= Stirling numbers of the second kind
{c}
{title2=$\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$}
{wiki}
= Stirling number of the second kind
{c}
{synonym}
For <nonnegative integers> $n,k$, the <Stirling number of the second kind>
$$
S(n,k)=\left\{\begin{matrix}n\\k\end{matrix}\right\}
$$
counts the <set partitions> of an $n$-element <finite set> into exactly $k$ unlabelled <blocks of a set partition>. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\geq1$. Grassl and Levin develop these counts through explicit <set partitions> and a <recurrence relation>. https://discrete.openmathbooks.org/more/mdm/sec_adv-partitions.html[Grassl and Levin, More Discrete Mathematics via Graph Theory, section 3.1: counting partitions]{ref}
\b[Insert one distinguished element.] For $n\geq1$ and $1\leq k\leq n$, the <Stirling numbers of the second kind> obey
$$
S(n,k)=kS(n-1,k)+S(n-1,k-1).
$$
\b[Proof outline.] Inspect the <block of a set partition> containing $n$. If it contains another element, removing $n$ leaves a <set partition> into $k$ <blocks of a set partition>; conversely, insert $n$ into any of those $k$ <blocks of a set partition>. If $n$ is alone, remove its <singleton set> and obtain a <set partition> into $k-1$ <blocks of a set partition>. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the <blocks of a set partition> have no names. https://discrete.openmathbooks.org/more/mdm/sec_adv-stirling.html[Grassl and Levin, More Discrete Mathematics via Graph Theory, section 3.4: Stirling recurrence]{ref}
For $n=4,k=2$, start with the three two-block <set partitions> of $\{1,2,3\}$. Inserting $4$ into either <block of a set partition> gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a <singleton set>. Hence $S(4,2)=2\cdot3+1=7$. The seven <set partitions> in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.
\Image[/set-partitions-stirling-insert-four.png]
{title=Exact construction of all seven two-block <set partitions> of $\{1,2,3,4\}$: six insert $4$ into an existing <block of a set partition>, and one creates a <singleton set>}
\b[Three different counting questions.] The <binomial coefficient> $\binom nk$ selects one $k$-element <subset>. The <Stirling number of the second kind> $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed <blocks of a set partition>. The power $k^n$ counts all <functions> to a specified $k$-element <finite set>, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.
\b[When the destinations have labels.] For fixed <finite sets> $X,Y$ of sizes $n,k$, respectively, the number of <surjective functions> $X\to Y$ is
$$
\#\{f:X\to Y\mid f\text{ is surjective}\}=k!S(n,k).
$$
Here every element of $Y$ must be used. Each <surjective function> gives a <set partition> of $X$ into its nonempty <preimages> $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ <blocks of a set partition> in $k!$ ways, where $k!$ is a <factorial>. For two labelled teams of four people this gives $2!\cdot7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary <function> counts by $k!$ fails in general because unused labels can be permuted without changing a <function>. For example, $3^4/3!=13.5$ cannot count <set partitions>. The empty-to-empty <function> is a <surjection>, consistent with $0!S(0,0)=1$. Stanley gives the <bijection> underlying this qualification.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[section 1.9: Twelvefold Way entry 3]{ref}
For example, the <inclusion-exclusion principle> counts the <surjections> from four elements to three labelled destinations as $3^4-3\cdot2^4+3\cdot1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element <block of a set partition> in $\binom42=6$ ways; the other two elements form <singleton sets>.
\b[Why these numbers also occur in algebra.] Classifying all <functions> to an $m$-element <finite set> by the size $k$ of their <image> gives
$$
m^n=\sum_{k=0}^n S(n,k)(m)_k,\qquad (m)_k=m(m-1)\cdots(m-k+1),\quad (m)_0=1.
$$
For a fixed <set partition>, the <falling factorial> $(m)_k$ counts assignments of distinct labels to its $k$ <blocks of a set partition>, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot4+3\cdot12+1\cdot24$. Replacing $m$ by $x$ yields a <polynomial> identity: both sides agree at every <nonnegative integer>. Thus the <Stirling numbers of the second kind> translate powers into <falling factorials>. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the <Bell number>.
Back to article page
