Definition:Stirling Numbers of the Second Kind
Definition
Let:
- $\delta_{n k}$ denote the Kronecker delta
- $n$ and $k$ be non-negative integers.
Definition 1
Stirling numbers of the second kind are defined recursively by:
- $\ds {n \brace k} := \begin{cases}
\delta_{n k} & : k = 0 \text{ or } n = 0 \\ & \\ \ds {n - 1 \brace k - 1} + k {n - 1 \brace k} & : \text{otherwise} \\ \end{cases}$
Definition 2
Stirling numbers of the second kind are defined as the coefficients $\ds {n \brace k}$ which satisfy the equation:
- $\ds x^n = \sum_k {n \brace k} x^{\underline k}$
where $x^{\underline k}$ denotes the $k$th falling factorial of $x$.
Stirling's Triangle of the Second Kind
$\begin{array}{r|rrrrrrrrrr} n & {n \brace 0} & {n \brace 1} & {n \brace 2} & {n \brace 3} & {n \brace 4} & {n \brace 5} & {n \brace 6} & {n \brace 7} & {n \brace 8} & {n \brace 9} \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 1 & 7 & 6 & 1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 0 & 1 & 15 & 25 & 10 & 1 & 0 & 0 & 0 & 0 \\ 6 & 0 & 1 & 31 & 90 & 65 & 15 & 1 & 0 & 0 & 0 \\ 7 & 0 & 1 & 63 & 301 & 350 & 140 & 21 & 1 & 0 & 0 \\ 8 & 0 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 & 0 \\ 9 & 0 & 1 & 255 & 3025 & 7770 & 6951 & 2646 & 462 & 36 & 1 \\ \end{array}$
Extension to Complex Numbers
Donald E. Knuth, in his The Art of Computer Programming: Volume 1: Fundamental Algorithms, 3rd ed. of $1997$, suggests an extension of the Stirling numbers of the second kind $\ds {r \brace r - m}$ to the real and complex numbers.
However, beyond stating that such a number is a polynomial in $r$ of degree $2 m$, and providing a few examples, he goes no further than that, and the details of this extension are unclear.
Notation
The notation $\ds {n \brace k}$ for Stirling numbers of the second kind is that proposed by Jovan Karamata and publicised by Donald E. Knuth.
Other notations exist.
Usage is inconsistent in the literature.
Examples
$5$th Power
- $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$
Also see
- Results about Stirling numbers (of both the first and second kind) can be found here.
Source of Name
This entry was named for James Stirling.
Technical Note
The $\LaTeX$ code for \(\ds {n \brace k}\) is \ds {n \brace k} .
The braces around the n \brace k are important.
The \ds is needed to create the symbol in its proper house display style.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients