# Generating Function for Elementary Symmetric Function

Jump to navigation
Jump to search

## Theorem

Let $a, b \in \Z$ be integers such that $b \ge a$.

Let $U$ be a set of $n = b - a + 1$ numbers $\left\{ {x_a, x_{a + 1}, \ldots, x_b}\right\}$.

Let $m \in \Z_{>0}$ be a (strictly) positive integer.

Let $a_m$ be an elementary symmetric function:

- $a_m = \displaystyle \sum_{a \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le b} x_{j_1} x_{j_2} \cdots x_{j_m}$

Let $G \left({z}\right)$ be a generating function for the sequence $\left\langle{a_m}\right\rangle$.

Then:

- $G \left({z}\right) = \displaystyle \prod_{k \mathop = a}^b \left({1 + x_k z}\right)$

## Proof

We have by definition of generating function that:

- $G \left({z}\right) = \displaystyle \sum_{n \mathop \ge 0} a_n z^n$

We have that:

- $a_0 = 1$

Suppose $a = b$.

Let $G_a \left({z}\right)$ be the generating function for $\left\langle{a_m}\right\rangle$ under this condition.

Then:

- $a \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le a$

can be fulfilled by only one set $\left\{ {j_1, j_2, \ldots, j_m}\right\}$, that is:

- $j_1 = a$

Thus in this case:

\(\displaystyle a_m\) | \(=\) | \(\displaystyle x_a \delta_{m 1}\) | where $\delta_{m 1}$ is the Kronecker delta. | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle G_a \left({z}\right)\) | \(=\) | \(\displaystyle \sum_{n \mathop \ge 0} x_a \delta_{n 1} z^n\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle G_a \left({z}\right)\) | \(=\) | \(\displaystyle 1 + x_a z\) |

Then by Product of Generating Functions, it follows that:

- $G \left({z}\right) = \left({1 + x_a z}\right) \left({1 + x_{a + 1} z}\right) \cdots \left({1 + x_b z}\right)$

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: Exercise $10$