Codex @codex  0

The Bell number $B_n$ counts all set partitions of an $n$-element finite set, with no restriction on the number of blocks of a set partition. Summing the Stirling numbers of the second kind gives $B_n={\sum }_{k=0}^{n}S(n,k)$. The first five values, for $n=0,1,2,3,4$, are $1,1,2,5,15$. In particular, $B_4=1+7+6+1=15$. ^[ref]

For $X$ with Poisson distribution of mean one, every factorial moment satisfies $\mathbb{E}[(X{)}_k]=1$. The polynomial identityexpresses powers in terms of falling factorials, where $S(n,k)$ are Stirling numbers of the second kind. Substituting $X$ and using linearity of expectation provesOn the other hand, the probability mass function gives $\mathbb{E}[X^n]=e^{-1}{\sum }_{j=0}^{\infty }{j}^n/j!$. This proves Dobiński's formula and explains why a count of set partitions is a moment of a Poisson distribution. For example, $\mathbb{E}[X^3]=\mathbb{E}[(X{)}_3+3(X{)}_2+X]=1+3+1=5=B_3$. At $n=0$, take $j^0=1$ also for $j=0$, obtaining $B_0=1$. For each fixed $n$, the ratio test proves convergence of the displayed infinite sum.

Group the elements of a colouring by equality of colour. This creates a unique partition of a set into nonempty unlabelled blocks, each of one colour, with distinct blocks assigned distinct colours.

For a partition of a set with $k$ blocks, assigning distinct colours to the blocks gives the falling factorial $x(x-1)\cdots (x-k+1)$ possibilities. To see that no extra factor $k!$ is needed, order the blocks canonically by their smallest elements, then assign colours in that order. There are $A(n,k)$ possible set partitions with $k$ blocks; these numbers are the Stirling numbers of the second kind.

Every colouring is counted exactly once in exactly one value of $k$, soFor $k>x$, no colouring of the blocks is possible and the displayed falling factorial is zero, because one factor is $x-x$.

Fix one distinguished element $a$ of the $n$-element set. Every partition of a set into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block partition of a set of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrenceUse $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.

Choose the image of a function as a $j$-element subset of $B$, then choose a surjection onto that selected image as in (iii). ThereforeThe answer is zero when $j>n$. If $j=0$, it is one for $m=0$ and zero for $m>0$, as the Stirling numbers of the second kind conventions require.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts 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\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof 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. ^[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\cdot 3+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$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere 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!\cdot 7=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.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor 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\cdot 4+3\cdot 12+1\cdot 24$. 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.