TAOCP 1.2.6 Exercise 39

Let $\left[{n \atop k}\right]$ denote the numbers in Stirling's first triangle.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.6: Binomial Coefficients

Exercise 39. [M10] What is the sum $\sum_k \left[{n \atop k}\right]$ of the numbers in each row of Stirling's first triangle? What is the sum of these numbers with alternating signs?

Verified: no
Solve time: -

Let $\left[{n \atop k}\right]$ denote the numbers in Stirling's first triangle. By the interpretation of $\left[{n \atop k}\right]$ as the number of permutations of $n$ elements having exactly $k$ cycles, every permutation contributes to exactly one value of $k$. Since there are $n!$ permutations of $n$ elements, the sum of the entries in row $n$ is

$$ \sum_k \left[{n \atop k}\right] = n!. $$

The alternating sum is obtained from the generating formula

$$ x(x+1)\cdots(x+n-1) = \sum_k \left[{n \atop k}\right]x^k. $$

Substituting $x=-1$ gives

$$ (-1)\cdot 0\cdot 1\cdots(n-2) = \sum_k \left{n \atop k}\right^k. $$

Hence, for $n\ge 2$,

$$ \sum_k \left{n \atop k}\right^k = 0. $$

For completeness, when $n=0$ the sum is $1$, and when $n=1$ it is $-1$. Thus the answer is

$$ \boxed{ \sum_k \left[{n \atop k}\right] = n!, \qquad \sum_k \left{n \atop k}\right^k = \begin{cases} 1, & n=0,\ -1, & n=1,\ 0, & n\ge 2. \end{cases} } $$