TAOCP 1.2.9 Exercise 10

Exercise 10. [M25] An elementary symmetric function is defined by the formula

$$ e_m = \sum_{1 \le j_1 < \cdots < j_m \le n} x_{j_1}\cdots x_{j_m}. $$

(This is the same as $h_m$ of Eq. (33), except that equal subscripts are not allowed.) Find the generating function for $e_m$, and express $e_m$ in terms of the $S_j$ in Eq. (34). Write out the formulas for $e_1,e_2,e_3,$ and $e_4$.

Verified: yes
Solve time: 2m04s

Solution

Let

$$ E(z)=\sum_{m\ge0} e_m z^m $$

be the generating function for the elementary symmetric functions. By definition,

$$ e_m=\sum_{1\le j_1<\cdots<j_m\le n}x_{j_1}\cdots x_{j_m}. $$

For each variable $x_i$, the factor $(1+x_i z)$ contributes either $1$ or $x_i z$. Hence

$$ \prod_{i=1}^{n}(1+x_i z) $$

expands into a sum in which the coefficient of $z^m$ is obtained by choosing $x_i z$ from exactly $m$ factors and $1$ from the remaining factors. Therefore the coefficient of $z^m$ is precisely $e_m$. Thus

$$ E(z)=\prod_{i=1}^{n}(1+x_i z). $$

This is the generating function for the elementary symmetric functions.

To express $e_m$ in terms of the power sums

$$ S_j=\sum_{i=1}^{n}x_i^j, $$

take logarithms:

$$ \ln E(z) =\sum_{i=1}^{n}\ln(1+x_i z). $$

Using Eq. (24),

$$ \ln(1+t) =\sum_{k\ge1}\frac{(-1)^{k+1}}{k}t^k, $$

with $t=x_i z$, we obtain

$$ \ln E(z) =\sum_{i=1}^{n}\sum_{k\ge1} \frac{(-1)^{k+1}}{k}x_i^k z^k =\sum_{k\ge1} \frac{(-1)^{k+1}}{k}S_k z^k. $$

Hence

$$ E(z) =\exp!\left( \sum_{k\ge1} \frac{(-1)^{k+1}}{k}S_k z^k \right). $$

This is the analogue of Eq. (35), with alternating signs.

To obtain explicit formulas, write

$$ A(z)=\sum_{k\ge1} \frac{(-1)^{k+1}}{k}S_k z^k =S_1z-\frac12S_2z^2+\frac13S_3z^3-\frac14S_4z^4+\cdots. $$

Since

$$ E(z)=e^{A(z)} =1+A+\frac{A^2}{2!}+\frac{A^3}{3!}+\frac{A^4}{4!}+\cdots, $$

the coefficients of successive powers of $z$ are as follows.

For $z^1$,

$$ e_1=S_1. $$

For $z^2$,

$$ e_2=-\frac12S_2+\frac12S_1^2 =\frac12\bigl(S_1^2-S_2\bigr). $$

For $z^3$,

$$ e_3=\frac13S_3-\frac12S_1S_2+\frac16S_1^3 =\frac16\bigl(S_1^3-3S_1S_2+2S_3\bigr). $$

For $z^4$,

$$ e_4 =-\frac14S_4 +\frac18S_2^2 +\frac13S_1S_3 -\frac14S_1^2S_2 +\frac1{24}S_1^4, $$

hence

$$ e_4 = \frac1{24} \bigl( S_1^4 -6S_1^2S_2 +3S_2^2 +8S_1S_3 -6S_4 \bigr). $$

Therefore

$$ \boxed{ \sum_{m\ge0}e_m z^m = \prod_{i=1}^{n}(1+x_i z) = \exp!\left( \sum_{k\ge1} \frac{(-1)^{k+1}}{k}S_k z^k \right) } $$

and

$$ \boxed{e_1=S_1,} $$

$$ \boxed{e_2=\frac12(S_1^2-S_2),} $$

$$ \boxed{e_3=\frac16(S_1^3-3S_1S_2+2S_3),} $$

$$ \boxed{ e_4= \frac1{24} \left( S_1^4 -6S_1^2S_2 +3S_2^2 +8S_1S_3 -6S_4 \right). } $$