More on Exponential Generating Functions

Recall from the Exponential Generating Functions page that if $(a_i)_{i=0}^{\infty} = (a_0, a_1, a_2, ...)$ is a sequence of real numbers then the exponential generating function of $(a_i)_{i=0}^{\infty}$ is given by:

(1)

\begin{align} \quad E(x) = \sum_{i=0}^{\infty} a_i \frac{x^i}{i!} = a_0 + a_1x + a_2 \frac{x^2}{2!} + ... + a_i \frac{x^i}{i!} + ... \end{align}

We noted that exponential generating functions are useful when the terms $a_i$ of $(a_i)_{i=0}^{\infty}$ arise from counting permutations.

We will now look further into exponential generating functions. Consider the following multiset with a finite number $k$ of distinct terms and finite repetition numbers $r_1, r_2, ..., r_n$:

(2)

\begin{align} \quad A = \{r_1 \cdot x_1, r_2 \cdot x_2, ..., r_k \cdot x_k \} \end{align}

Suppose that we want to create a sequence $(a_n)_{n=0}^{\infty} = (a_0, a_1, a_2, ..., a_n, ...)$ where for each $n \in \{0, 1, 2, ... \}$ the term $a_i$ counts the number of $n$-permutations of elements from the multiset $A$. What will the exponential generating function for $(a_n)_{n=0}^{\infty}$ therefore look like? The following theorem answers this question.

Theorem 1: Let $A = \{ r_1 \cdot x_1, r_2 \cdot x_2, ..., r_k \cdot x_k \}$ be a multiset with a finite number of distinct terms $k$, and such that the repetition numbers $r_1, r_2, ..., r_k$ of $A$ are finite. Define $(a_n)_{n=0}^{\infty} = (a_0, a_1, a_2, ..., a_n, ...)$ to be a sequence of nonnegative integers where each term $a_n$ counts the number of $n$-permutations of elements from $A$ for each $n \in \{0, 1, 2, ... \}$. For each $i \in \{1, 2, ..., k \}$ define $E_{r_i}(x) = 1 + x + \frac{x^2}{2!} + ... + \frac{x^{r_i}}{r_i!}$. Then the generating function of $(a_n)_{n=0}^{\infty}$ is given by $E(x) = E_{r_1}(x) \cdot E_{r_2}(x) \cdot ... \cdot E_{r_k}(x)$.

Theorem 1 also applies if some of the repetition numbers $r_1, r_2, ..., r_k$ are $\infty$ since we then define $E_{\infty} = 1 + x + \frac{x^2}{2!} + ... = \sum_{i=0}^{\infty} \frac{x^i}{i!} = e^x$ which is valid for all $x \in \mathbb{R}$.

• Consider the expansion of the product $E_{r_1}(x) \cdot E_{r_2}(x) \cdot ... \cdot E_{r_k}(x)$:

(3)

\begin{align} \quad E_{r_1}(x) \cdot E_{r_2}(x) \cdot ... \cdot E_{r_k}(x) = \left (1 + x + \frac{x^2}{2!} + ... + \frac{x^{r_1}}{r_1!} \right ) \left ( 1 + x + \frac{x^2}{2!} + ... + \frac{x^{r_2}}{r_2!} \right ) ... \left ( 1 + x + \frac{x^2}{2!} + ... + \frac{x^{r_k}}{r_k!} \right ) \end{align}

• For $0 \leq b_1 \leq r_1$, $0 \leq b_2 \leq r_2$, …, $0 \leq b_k \leq r_k$, each term in the product above will be of the form:

(4)

\begin{align} \quad \frac{x^{b_1}}{b_1!} \cdot \frac{x^{b_2}}{b_2!} \cdot ... \cdot \frac{x^{b_k}}{b_k!} = \frac{x^{b_1 + b_2 + ... + b_k}}{b_1! \cdot b_2! \cdot ... \cdot b_k!} \end{align}

• Now we want each term $a_n$ in the sequence $(a_n)_{n=0}^{\infty}$ to represent the number of $n$-permutations of elements in the multiset $A$. Therefore, we let $b_1 + b_2 + ... + b_k = n$. Therefore:

(5)

\begin{align} \quad \frac{x^{b_1 + b_2 + ... + b_k}}{b_1! \cdot b_2! \cdot ... \cdot b_k!} = \frac{x^n}{b_1! \cdot b_2! \cdot ... \cdot b_k!} = \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_k!} \cdot \frac{x^n}{n!} \end{align}

• Now define the set $B$ as follows:

(6)

\begin{align} \quad B = \{ (b_1, b_2, ..., b_k) : 0 \leq b_1 \leq r_1, 0 \leq b_2 \leq r_2, ..., 0 \leq b_k \leq r_k, b_1 + b_2 + ... + b_k = n \} \end{align}

• The coefficient on the term $\frac{x^n}{n!}$ when the expansion of $E_{r_1}(x) \cdot E_{r_2}(x) \cdot ... \cdot E_{r_k}(x)$ is simplified will be:

(7)

\begin{align} \quad \sum_{(b_1, b_2, ..., b_k) \in B} \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_k!} = \sum_{(b_1, b_2, ..., b_k) \in B} \binom{n}{b_1, b_2, ..., b_k} \end{align}

• These coefficients are merely the number of $n$-permutations of the submultiset $\{b_1 \cdot x_1, b_2 \cdot x_2, ..., b_k \cdot x_k \}$ of $A$. So the total number of $n$-permutations of $A$ is equal to the total number of all $n$-permutations of all submultisets such that $b_1 + b_2 + ... + b_k = n$ which the sum above accounts for. Therefore, for each $n \in \{0, 1, 2, ... \}$ we have that:

(8)

\begin{align} \quad a_n = \sum_{(b_1, b_2, ..., b_k) \in B} \binom{n}{b_1, b_2, ..., b_k} \end{align}

• Since $\sum_{(b_1, b_2, ..., b_k) \in B} \binom{n}{b_1, b_2, ..., b_k}$ is also the coefficient of $\frac{x^n}{n!}$ after simplification of the expansion of $E_{r_1} \cdot E_{r_2} \cdot ... \cdot E_{r_k}$ we have that the generating function $E(x)$ of $(a_n)_{n=0}^{\infty}$ is given by:

(9)

\begin{align} \quad E(x) = E_{r_1}(x) \cdot E_{r_2}(x) \cdot ... \cdot E_{r_k}(x) \quad \blacksquare \end{align}