Exercise 15, § 6

Let $T$ be a finite set with $k$ elements. We denote by $D_k$ the set of elements $(a_1, \ldots, a_k)$ of $\mathbf{N}^k$ such that $a_1 + \ldots + a_k = k$ and $a_1 \geq a_2 \geq \ldots \geq a_k$. With every equivalence relation R in T we associate an element $\lambda(R)$ of $D_k$ as follows: if $U_1, ..., U_l$ are the equivalence classes under R, numbered so that $\mathrm{Card}(U_i) \geq ... \geq \mathrm{Card}(U_l)$, put $\lambda(R) = (\alpha_1, ..., \alpha_k)$ with $\alpha_i = \mathrm{Card}(U_i)$ if $1 \leq i \leq l$ and $\alpha_i = 0$ if $1 < i \leq k$. Let $X_n$ ($n \in \mathbf{N}$) be indeterminates; for each $R \in \mathscr{H}(T)$ put $r(R) = \sum_{f} \prod_{i \in I} X_{f(i)}$, where the summation is extended to the set of mappings $f : T \to \mathbf{N}$ such that R is the equivalence relation associated with $f$. Put $s(R) = \sum_{S \neq R} r(S)$.

a) Prove that $r(R) = \prod_{i=1}^{k} r_i . M(\lambda(R))$ if $r_i$ of the equivalence classes under R arc of cardinal i for $1 \leq i \leq k$. (See formula (11) of IV, p. 65 for the definition of $M(\alpha)$.)

b) Prove the relation $S(R) = \prod_{i=1}^{k} p_i^{r_i}$ where the $r_i$ are as in a) and $p_m = \sum_{n \in \mathbf{N}} X_n^m$ for every integer $m \geq 1$.

c) Show that $r(R) = \sum_{S \neq R} \mu(R, S) s(S)$, where $\mu(R, S)$ is defined as in Exercise 14.

d) Hence deduce an expression of the $s_k$ as a polynomial in $p_1, ..., p_k$ with rational coefficients, where $s_k = \sum_{i_1 < ... < i_k} X_{i_1} ... X_{i_k}$.

e) For $a \in D_k$ put $S'(\alpha) = \prod_{i=1}^{k} s_{\alpha_i}$. Show that $S'(\alpha) = \sum_{\beta \in D_k} c'_{\alpha \beta} . M(\beta)$, where the integer $c'_{\alpha \beta}$ is defined as follows: suppose that $r_i$ (resp. $s_i$) of the components of $a$ (resp. $\beta$) are equal to i (for $1 \leq 1 \leq k$). Then $c'_{\alpha \beta}$ is the product $Nr,!... r_k!s_1!... s_k!/k!$, where N is the number of pairs of equivalence relations R, S on T such that $\lambda(R) = a, \lambda(S) = \beta$ and such that the intersection of an equivalence class under R with an equivalence class under S has at most one element. Deduce the symmetry relation $c'_{\alpha \beta} = c'_{\beta \alpha}$.

f) Show that there is an involution $a \mapsto \tilde{\alpha}$ in $D_k$, characterized by the fact that the relations $i \leq a,$ and $j \leq \tilde{\alpha}_i$ are equivalent, for i, j in the range from 1 to k. Show that $S'(\alpha) = S(\tilde{\alpha})$ and $c'_{\alpha \beta} = c_{\tilde{\alpha} \tilde{\beta}}$. Hence obtain the relation $c_{\alpha \beta} = c_{\tilde{\alpha} \tilde{\beta}}$ (with the notation of IV, p. 66).

Conventions (cf. page IV, 66).

A symbol such as $p^\alpha \cdot q^\beta \ldots$, where $p, q, \alpha, \beta, \ldots$ are integers $\geq 1$, denotes an element of $D_k$ where $k = p\alpha + q\beta + \ldots$ having $\alpha$ components equal to $p$, $\beta$ components equal to $q$, etc. Thus $3 \cdot 1^2$ denotes the element of $D_5$ equal to $(3, 1, 1, 0, 0)$, while $1^4$ denotes the element $(1, 1, 1, 1)$ of $D_r$.

On the right of the row of index $\alpha$ of the matrix C the expression of $S(\alpha)$ as monomial in $s_1, \ldots, s_k$ is given. For example, for $k = 3$ and $\alpha = 2 . 1$ we have

We have used a corresponding convention for the columns of the matrix D. For example, for $k = 4$ and $\alpha = 2^2$ we have

We recall that $M(2^2)$ is the sum of all monomials of the form $X_i^2 X_j^2$ for $1 \leq i < j \leq n$ in the ring $\mathbf{Z}[X_1, \ldots, X_n]$.

An empty box indicates a zero element of the matrices C and D.

k = 2 2 1^2 2 1 2 S_1^2 1^2 1 S_2

2 1^2 2 1 -2 1^2 1 S_1^2 S_2

k = 3 3 2.1 1^3 3 1 3 6 S_1^3 2.1 1 3 S_1 S_2 1^3 1 S_3

3 2.1 1^3 3 1 -3 3 2.1 1 -3 1^3 1 S_1^3 S_1 S_2 S_3

k = 4 4 3.1 2^2 2.1^2 1^4 4 1 4 6 12 24 S_1^4 3.1 1 2 5 12 S_1^2 S_2 2^2 1 2 6 S_2^2 2.1^2 1 4 S_1 S_3 1^4 1 S_4

Matrix C

4 3.1 2^2 2.1^2 1^4 4 1 -4 2 4 -4 3.1 1 -2 -1 4 2^2 1 -2 2 2.1^2 1 -4 1^4 1

S_1^4 S_1^2 S_2 S_2^2 S_1 S_3 S_4 Matrix D

TABLE

k = 5 5 4.1 3.2 3.1^2 2^2.1 2.1^3 1^5 5 1 5 10 20 30 60 120 S_1^5 4.1 1 3 7 12 27 60 S_1^3 S_2 3.2 1 2 5 12 30 S_1 S_2^2 3.1^2 1 2 7 20 S_1^2 S_3 2^2.1 1 3 10 S_2 S_3 2.1^3 1 5 S_1 S_4 1^5 1 S_5

Matrix C

5 4.1 3.2 3.1^2 2^2.1 2.1^3 1^5 5 1 -5 5 5 -5 -5 5 4.1 1 -3 -1 5 1 -5 3.2 1 -2 -1 5 -5 3.1^2 1 -2 -1 5 2^2.1 1 -3 5 2.1^3 1 -5 1^5 1

S_1^5 S_1^3 S_2 S_1 S_2^2 S_1^2 S_3 S_2 S_3 S_1 S_4 S_5 Matrix D