From Generating Function to Explicit Formula : Finding Coefficients

455 Views Asked by At

There're lots of cases that generating function doesn't explicitly reveals the coefficient for $x^n$ or $x^n/n!$

For example, the case of the Stirling number of the second kind, I had derived following generating function:

$$\sum_{n≥0}S(n, k)x^n = {x^k\over (1−x)(1−2x)···(1−kx)}$$

from the recurrence relation $G_k(x) =xG_{k-1}(x) + kxG_k(x)$ where $G_k(x) = \sum_{n≥0}S(n, k)x^n$

Now, I want to properly manipulate ${x^k\over (1−x)(1−2x)···(1−kx)}$ so that I could find $S(n,k)$ in explicit formula.

Any guidance to proceed how to change given polynomial?

1

There are 1 best solutions below

2
On

You can compute the partial fraction decomposition; this works more generally for any rational generating function, and actually this is one of the few cases in which it's straightforward to extract a closed form from a generating function.

We have

$$\frac{x^k}{(1 - x) \dots (1 - kx)} = \frac{(-1)^k}{k!} + \sum_{i=1}^k \frac{c_i}{1 - ix}$$

for some coefficients $c_i$, which can be computed as follows. We can multiply both sides by $1 - ix$, then substitute $x = \frac{1}{i}$, which gives, after some mild algebraic manipulations,

$$c_i = \frac{1}{\prod_{0 \le j \neq i \le k} (i - j)} = \frac{(-1)^{k-i}}{i! (k-i)!}$$

This gives

$$\frac{x^k}{(1 - x) \dots (1 - kx)} = \sum_{i=0}^k \frac{(-1)^{k-i}}{i! (k-i)!} \frac{1}{1 - ix}$$

(note that the sum now starts at $i = 0$ to accommodate the constant term), and computing the coefficient of $x^n$ on both sides gives

$$\boxed{ S(n, k) = \frac{1}{k!} \sum_{i=0}^k (-1)^{k-i} {k \choose i} i^n }.$$

You can see this formula, for example, on Wikipedia.