Set Partitions, Stirling Numbers and Exponential Generating Functions — Examples

The partitions of $[4]$ are:

• one block: $\{\{1,2,3,4\}\}$;
• two blocks: $\{\{1\},\{2,3,4\}\}$, $\{\{2\},\{1,3,4\}\}$, $\{\{3\},\{1,2,4\}\}$, $\{\{4\},\{1,2,3\}\}$, $\{\{1,2\},\{3,4\}\}$, $\{\{1,3\},\{2,4\}\}$, $\{\{1,4\},\{2,3\}\}$;
• three blocks: $\{\{1\},\{2\},\{3,4\}\}$, $\{\{1\},\{3\},\{2,4\}\}$, $\{\{1\},\{4\},\{2,3\}\}$, $\{\{2\},\{3\},\{1,4\}\}$, $\{\{2\},\{4\},\{1,3\}\}$, $\{\{3\},\{4\},\{1,2\}\}$;
• four blocks: $\{\{1\},\{2\},\{3\},\{4\}\}$.

So

$S(4,1)=1,S(4,2)=7,S(4,3)=6,S(4,4)=1,$

and therefore $B_4=1+7+6+1=15$.

Three standard computations agree:

1. recurrence: $S(4,2)=2S(3,2)+S(3,1)=2\cdot 3+1=7;$
2. inclusion-exclusion: $S(4,2)=\frac{1}{2!}(2^4-2\cdot 1^4)=\frac{14}{2}=7;$
3. direct listing: The set partitions of $[4]$ grouped by their number of blocks shows exactly seven two-block partitions of $[4]$.

Thus all three routes give the same value $S(4,2)=7$.

For $0\le n,k\le 4$, the lower-triangular matrices are

$S=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 1& 3& 1& 0\\ 0& 1& 7& 6& 1\end{array}\right),s=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& -1& 1& 0& 0\\ 0& 2& -3& 1& 0\\ 0& -6& 11& -6& 1\end{array}\right)\mathrm{.}$

Multiplying them gives the $5\times 5$ identity matrix, which is the concrete size-$4$ instance of The signed first-kind and second-kind Stirling numbers are inverse transition matrices.

For $[3]$, the Bell number is

$B_3=S(3,1)+S(3,2)+S(3,3)=1+3+1=5.$

The ordered Bell number is larger because each partition with $k$ blocks can be ordered in $k!$ ways:

$1\cdot 1!+3\cdot 2!+1\cdot 3!=1+6+6=13.$

So the ordered Bell sequence already differs from the Bell sequence at $n=3$.

The involutions of $[4]$ are exactly the permutations whose cycle lengths are all $1$ or $2$:

• one with four fixed points: $()$;
• six with one transposition: $(12)$, $(13)$, $(14)$, $(23)$, $(24)$, $(34)$;
• three with two disjoint transpositions: $(12)(34)$, $(13)(24)$, $(14)(23)$.

Hence $I_4=1+6+3=10$, agreeing with the EGF $\exp (x+x^2\mathrm{/}2)$ from Standard labelled specializations give involutions, ordered Bell numbers, and partitions without singletons.

The closed formula gives

$L(4,2)=\frac{4!}{2!}\left(\genfrac{}{}{0px}{}{3}{1}\right)=12\cdot 3=36.$

So there are $36$ partitions of $[4]$ into two nonempty blocks when each block is internally linearly ordered.

The partitions of $[4]$ with every block of size at least $2$ are:

$\{\{1,2,3,4\}\},\{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\}\mathrm{.}$

So the count is $4$.

There is exactly one partition of $[n]$ into singleton blocks, namely

$\{\{1\},\{2\},\dots ,\{n\}\}\mathrm{.}$

So the counting sequence is constantly $1$, and the corresponding exponential generating function is

${\sum }_{n\ge 0}\frac{x^n}{n!}=e^x\mathrm{.}$

False claim: the Bell number $B_n$ counts ordered set partitions of $[n]$.

False claim: for all $n,k$, the number $S(n,k)$ is the number of surjections $[n]\to [k]$.

False claim: whenever two labelled classes $\mathcal{A}$ and $\mathcal{B}$ are combined in any way, the exponential generating function of the result is the product of the EGFs of $\mathcal{A}$ and $\mathcal{B}$.

Refuted claim: a set partition is determined by the multiset of its block sizes.

Refuted claim: the inclusion-exclusion formula for $S(n,k)$ also counts permutations of $[n]$ with exactly $k$ cycles.