Definition:Stirling Numbers of the Second Kind

From ProofWiki
Jump to navigation Jump to search

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:

$\displaystyle {n \brace k} := \begin{cases} \delta_{n k} & : k = 0 \text{ or } n = 0 \\ & \\ \displaystyle {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 $\displaystyle {n \brace k}$ which satisfy the equation:

$\displaystyle 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 $\displaystyle {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 $\displaystyle {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 \(\displaystyle {n \brace k}\) is \displaystyle {n \brace k} .

The braces around the n \brace k are important.

The \displaystyle is needed to create the symbol in its proper house display style.


Sources