Generating Function for Elementary Symmetric Function/Outline

Theorem

Let $U$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.

Let $\map {e_m} U$ be the elementary symmetric function of degree $m$ on $U$:

\(\ds \map {e_m} U\)

\(=\)

\(\ds \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} \paren {\prod_{i \mathop = 1}^m x_{j_i} }\)

\(\ds \)

\(=\)

\(\ds \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} x_{j_1} x_{j_2} \cdots x_{j_m}\)

Let $a_m := \map {e_m} U$ for $m = 0, 1, 2, \ldots$

Let $\map G z$ be a generating function for the sequence $\sequence {a_m}$:

$\ds \map G z = \sum_{m \mathop = 0}^\infty a_m z^m$

Then:

$\ds \map G z = \prod_{k \mathop = 1}^n \paren {1 + x_k z}$

Outline

Generating function discovery methods can find a formula for $\map G z$.

Let $n = 1$.

Then $U$ is a singleton:

$U = \set {x_1}$.

Expand the formal series:

\(\ds \map G z\)

\(=\)

\(\ds \map {e_0} U + \map {e_1} z + \sum_{m \mathop = 2}^\infty 0 z^m\)

\(\ds \leadsto \ \ \)

\(\ds \)

\(=\)

\(\ds 1 + x_1 z\)

because $\map {e_0} U = 1$ and $\map {e_1} U = x_a$

Product of Generating Functions and experience with elementary symmetric functions suggests:

$\map G z = \paren {1 + x_1 z} \paren {1 + x_2 z} \cdots \paren {1 + x_n z}$