I am studying Introductory Combinatorics from Richard Brualdi but I am unable to think about a solution for this problem in exercises.
Problem is:
Compute the Stirling number of second kind $S(8, k)$ for $k=0, 1,2,…,8$.
My attempt:
Using combinatorial definition it is easy to derive $S(n, 1) = 1$ for
all $n\geq 1$, $S(n, 2) = 2^{n-1} – 1 . ( n\geq 2) , S( n, n-1)
= \binom n 2 $ and $S(n, n-2) = \binom n 3 + 3 \binom n 4$.Using these relations $S(8, k)$ can be easily calculated for $k=1,
2,7,8$.
$S(p, k) = k\cdot S(p-1, k) + S(p-1, k-1)$ can be used, but it will be really time consuming as I need to calculate $S(7, k) , S(6, k) \dots $ and so on.
My question is can anybody please tell some alternative approaches which is not time consuming?
I shall be really thankful.
Best Answer
Perhaps you are unaware about this approach, but we can solve this problem using generating functions and the fundamental recurrence for the Stirling numbers of the second kind. In fact, this is done as an example in the fantastic book by Herbert Wilf, Generatingfunctionology.
Let, $S(n, k) = {n \brace k}$ be the Stirling number of the second kind.
We have, for $n, k \gt 0$ that, $$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$$ with the initial value $S(0,0) = 1$.
Define the generating function $F_k(x) = \displaystyle \sum_{n \ge 0} S(n, k) x^n$
Then, from the recurrence relation, we get after summing over $n$, $$F_k(x) = xF_{k-1}(x) + kxF_k(x)$$ from which we have, $$F_k(x) = \dfrac{x}{1 - kx}F_{k-1}(x) = \displaystyle \prod_{r = 1}^k \dfrac{x}{1 - rx}$$ since the initial value is $F_0(x) = 1$.
Now, we need to do a partial fraction expansion of the denominator in the product to get the explicit formula.
Let, $\displaystyle \prod_{r = 1}^k \dfrac{1}{1 - rx} = \displaystyle \sum_{j = 1}^k \dfrac{p_j}{1 - jx}$
Cross-multiply one factor at a time and set that factor to zero. We easily get that, $$p_j = \displaystyle \prod_{r = 1}^{k; r \ne j} \dfrac{1}{1 - \frac{r}{j}} = (-1)^{k - j}\dfrac{j^k}{j! \cdot (k-j)!}$$
Hence, we have, $$F_k(x) = \displaystyle \sum_{n \ge 0} S(n, k) x^n = x^k \displaystyle \prod_{r = 1}^k \dfrac{1}{1 - rx}$$ $$\implies F_k(x) = x^k \displaystyle \sum_{j = 1}^k \dfrac{p_j}{1 - jx}$$ $$\implies F_k(x) = x^k \displaystyle \sum_{j = 1}^k p_j(1 + jx + j^2 x^2 + \dots)$$ $$\implies F_k(x) = \displaystyle \sum_{j = 1}^k p_j(x^k + j x^{k+1} + \dots)$$
The coefficient of $x^{k + r}$ on the right hand side is nothing but $\displaystyle \sum_{j = 1}^k p_j \cdot j^r$. Setting $k + r = n$ and using the definition of the generating function, we have, $$S(n, k) = \displaystyle \sum_{j = 1}^k p_j \cdot j^{n - k}$$ And using the expression for $p_j$, we finally get, $$S(n, k) = \displaystyle \sum_{j = 1}^k (-1)^{k - j}\dfrac{j^n}{j! \cdot (k-j)!}$$
Though it can't be said that computing the Stirling numbers using this formula is very efficient, the advantage is that this formula puts all problems like the one in Brualdi to rest at once. Hope it helps.