Stirling Numbers of the Second Kind/Examples/5th Power
Jump to navigation
Jump to search
Example of Stirling Numbers of the Second Kind
- $x^5 = x^{\underline 5} + 10 x^{\underline 4} + 25 x^{\underline 3} + 15 x^{\underline 2} + x^{\underline 1}$
and so:
- $x^5 = 120 \dbinom x 5 + 240 \dbinom x 4 + 150 \dbinom x 3 + 30 \dbinom x 2 + \dbinom x 1$
Proof
From the definition of Stirling numbers of the second kind:
- $\ds x^n = \sum_k {n \brace k} x^{\underline k}$
Reading the values directly from Stirling's triangle of the second kind:
\(\ds {5 \brace 5}\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds {5 \brace 4}\) | \(=\) | \(\ds 10\) | ||||||||||||
\(\ds {5 \brace 3}\) | \(=\) | \(\ds 25\) | ||||||||||||
\(\ds {5 \brace 2}\) | \(=\) | \(\ds 16\) | ||||||||||||
\(\ds {5 \brace 1}\) | \(=\) | \(\ds 1\) |
By definition of binomial coefficient:
\(\ds x^{\underline 5}\) | \(=\) | \(\ds 5! \dbinom x 5 = 120 \dbinom x 5\) | ||||||||||||
\(\ds x^{\underline 4}\) | \(=\) | \(\ds 4! \dbinom x 4 = 24 \dbinom x 4\) | ||||||||||||
\(\ds x^{\underline 3}\) | \(=\) | \(\ds 3! \dbinom x 3 = 6 \dbinom x 3\) | ||||||||||||
\(\ds x^{\underline 2}\) | \(=\) | \(\ds 2! \dbinom x 2 = 2 \dbinom x 2\) | ||||||||||||
\(\ds x^{\underline 1}\) | \(=\) | \(\ds 1! \dbinom x 1 = \dbinom x 1\) |
Hence:
- $x^5 = 120 \dbinom x 5 + 240 \dbinom x 4 + 150 \dbinom x 3 + 30 \dbinom x 2 + \dbinom x 1$
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients