Finding closed form of exponential generating function

1.3k Views Asked by At

Let $S(n, k)$ be the Stirling number of the second kind. For a fixed positive integer $k$, find a closed form for the exponential generating function $B(x) = \sum_{n\ge0}S(n,k)\frac{x^n}{n!}$.

I believe the closed form of

$$\sum_{n\ge0}n!\frac{x^n}{n!}$$

is $\frac{1}{1-x}$ but the inclusion of $S(n,k)$ confuses me.

1

There are 1 best solutions below

0
On

Stirling numbers of the second kind, $\genfrac{\{}{\}}{0pt}{}{n}{k}$, count the number of ways to divide a set of $n$ elements into $k$ classes. This gives, considering element $n$:

  • If $n$ is in a class by itself: This leaves $n - 1$ elements to group into $k - 1$ classes, $\genfrac{\{}{\}}{0pt}{}{n - 1}{k - 1}$ ways to do this
  • If $n$ is in a class with other elements: There are $n - 1$ other elements to divide into $k$ classes, $n$ can be in any one of them, $k \genfrac{\{}{\}}{0pt}{}{n - 1}{k}$ ways

Pulling this together gives the recurrence:

$\begin{align*} \genfrac{\{}{\}}{0pt}{}{n}{k} &= \genfrac{\{}{\}}{0pt}{}{n - 1}{k - 1} + k \genfrac{\{}{\}}{0pt}{}{n - 1}{k} \end{align*}$

As boundary conditions we have $\genfrac{\{}{\}}{0pt}{}{n}{0} = 0$ if $n > 0$, $\genfrac{\{}{\}}{0pt}{}{n}{n} = 1$.

To get an exponential generating function in $n$ for $\genfrac{\{}{\}}{0pt}{}{n}{k}$, call it $S_k(z) = \sum_{n \ge 0} \genfrac{\{}{\}}{0pt}{}{n}{k} \frac{z^n}{n!}$, multiply the shifted recurrence by $z^n / n!$ and sum over $n \ge 0$ and recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} \genfrac{\{}{\}}{0pt}{}{n + 1}{k} \frac{z^n}{n!} &= \sum_{n \ge 0} \genfrac{\{}{\}}{0pt}{}{n}{k - 1} \frac{z^n}{n!} + k \sum_{n \ge 0} \genfrac{\{}{\}}{0pt}{}{n}{k} \frac{z^n}{n!} \\ S_k'(z) &= S_{k - 1}(z) + k S_k(z) \end{align*}$

From the boundary conditions we know $S_0(z) = 1$ and $S_k(0) = 0$ if $k > 0$.

The solution to the differential equation is:

$\begin{align*} S_k(z) &= e^{k z} \int_0^z e^{-k t} S_{k - 1}(t) d t \end{align*}$

This gives:

$\begin{align*} S_0(z) &= 1 \\ S_1(z) &= e^z - 1 \\ S_2(z) &= \frac{(e^z - 1)^2}{2} \\ S_3(z) &= \frac{(e^z - 1)^3}{3!} \\ S_4(z) &= \frac{(e^z - 1)^4}{4!} \end{align*}$

Induction confirms that:

$\begin{align*} S_k(z) &= \frac{(e^z - 1)^k}{k!} \end{align*}$