Exercise 1552Combinatorics › Binomial coefficientsM1Added 3 Nov 2026

Stirling numbers and binomials

#Stirling#binomial#identity

Statement

Show that $x^n=\sum_{k=0}^{n}S(n,k)x(x-1)\cdots(x-k+1)$ where $S(n,k)$ is the Stirling number of the second kind.

Hint

Both sides count functions from an $n$ -set to an $x$ -set, classified by the size of the image.

Show solutionHide solution

Solution

Count 1. $x^n$ functions from $n$ -set to $x$ -set.

Count 2. Classify by image size $k$ . Choose the image ( $\binom{x}{k}$ ways), then a surjection onto it ( $S(n,k)\cdot k!$ ways). Total: $\sum_k\binom{x}{k}k!\,S(n,k)=\sum_k S(n,k)\,x(x-1)\cdots(x-k+1)$ .

Conclusion. $x^n=\sum_k S(n,k)x^{\underline{k}}$ .

Stirling numbers and binomials

Statement

Solution

More problems in Binomial coefficients