Set Partitions, Stirling Numbers and Exponential Generating Functions

If $n=0$, then $[n]=\mathrm{\varnothing }$, whose only partition is the empty family. So the statement holds in the empty-set boundary case.

Assume $n\ge 1$. For a partition $\mathcal{P}$ of $[n]$, define $f_{\mathcal{P}}:[n]\to [n]$ by sending each $i\in [n]$ to the least element of the block of $\mathcal{P}$ containing $i$. If $i$ and $j$ lie in the same block, then they have the same least block element. Conversely, if $f_{\mathcal{P}}(i)=f_{\mathcal{P}}(j)$, then both $i$ and $j$ lie in the block containing that common least element, so they lie in the same block. Thus $\mathcal{P}$ is recovered from the fibres of $f_{\mathcal{P}}$.

Therefore $\mathcal{P}\mapsto f_{\mathcal{P}}$ is injective from the set of partitions of $[n]$ into the function set $[n{]}^{[n]}$. By The set $A^B$ of functions $B\to A$ between finite sets is finite, with $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$, the latter is finite. Hence the set of all partitions of $[n]$ is finite, and every subfamily of it, including the partitions with exactly $k$ blocks, is finite as well.

Look at the block containing the element $n$. If that block is the singleton $\{n\}$, deleting it leaves a partition of $[n-1]$ into exactly $k-1$ blocks. Conversely, adjoining $\{n\}$ to any partition of $[n-1]$ into $k-1$ blocks produces such a partition of $[n]$. So the singleton case contributes $S(n-1,k-1)$.

If the block of $n$ is not a singleton, delete $n$ from that block. The remaining blocks form a partition of $[n-1]$ into exactly $k$ blocks, and the original partition is recovered by choosing one of those $k$ blocks and reinserting $n$ into it. So the nonsingleton case contributes $kS(n-1,k)$.

The two cases are disjoint and exhaustive, so their counts add to $S(n,k)$. This gives the displayed recurrence.

Let $S$ be the block containing $n+1$, and let $T:=[n]\setminus (S\setminus \{n+1\})$. Then $T$ is exactly the set of elements not lying in the distinguished block. If $\mathrm{\mid }T\mathrm{\mid }=k$, there are $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ choices for $T$, and after that the elements of $T$ may be partitioned arbitrarily in $B_k$ ways.

Conversely, every choice of a subset $T\subseteq [n]$ and a partition of $T$ determines a unique partition of $[n+1]$: put all elements of $[n]\setminus T$ together with $n+1$ into one block and keep the chosen partition of $T$ for the other blocks.

Summing over all possible values $k=\mathrm{\mid }T\mathrm{\mid }$ gives the claimed recurrence for $B_{n+1}$.

A partition of $[n]$ into exactly $k$ blocks becomes a surjection $[n]\to [k]$ once the $k$ blocks are labelled by the $k$ elements of $[k]$. Conversely, the fibres of a surjection $[n]\to [k]$ form a partition of $[n]$ into exactly $k$ nonempty blocks. Thus the number of surjections $[n]\to [k]$ is $k!S(n,k)$.

By The number of surjections from an $n$-element set onto a $k$-element set is ${\sum }_{i<k+1}(-1{)}^i\left(\genfrac{}{}{0px}{}{k}{i}\right)(k-i{)}^n$, read in $\mathbb{R}$ through $\iota$, that same number equals ${\sum }_{i=0}^k(-1{)}^i\left(\genfrac{}{}{0px}{}{k}{i}\right)(k-i{)}^n$. Therefore $k!S(n,k)={\sum }_{i=0}^k(-1{)}^i\left(\genfrac{}{}{0px}{}{k}{i}\right)(k-i{)}^n\mathrm{.}$

Dividing by the nonzero factorial $k!$ from The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$ gives the displayed formula.

The left-hand side $m^n$ counts all functions $[n]\to [m]$. Group those functions by the partition of $[n]$ into their nonempty fibres. If the image has size $k$, then the fibres form a partition of $[n]$ into $k$ blocks, counted by $S(n,k)$.

Once such a $k$-block partition is fixed, assigning distinct values of $[m]$ to its blocks is equivalent to choosing an ordered $k$-tuple of distinct elements of $[m]$, and there are exactly $m^{\underset{‾}{k}}$ such choices by The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$.

Summing over all possible image sizes $k$ counts every function $[n]\to [m]$ exactly once, so $m^n={\sum }_{k=0}^{n}S(n,k)m^{\underset{‾}{k}}$.

To build a permutation of $[n]$ with exactly $k$ cycles, start from a permutation of $[n-1]$. Either $n$ forms a new one-cycle, which contributes $c(n-1,k-1)$ possibilities, or else $n$ is inserted into one of the $n-1$ cyclic slots of a permutation with $k$ cycles, which contributes $(n-1)c(n-1,k)$. These two constructions are disjoint and exhaustive, so the recurrence follows.

Let $P_n(x):={\sum }_{k=0}^{n}c(n,k)x^k$. Step 1.1 gives $P_n(x)=x{P}_{n-1}(x)+(n-1)P_{n-1}(x)=(x+n-1)P_{n-1}(x)$, and also $P_0(x)=1$.

The rising factorial satisfies the same recursion: $x^{\bar{0}}=1$ and $x^{\bar{n}}=(x+n-1)x^{\overline{n-1}}$ by The rising factorial. Therefore $P_n(x)=x^{\bar{n}}$ for all $n$ by induction on $n$.

Replace $x$ by $-m$ in The signless first-kind Stirling numbers satisfy their recurrence and expand the rising factorial. Since $(-m{)}^{\bar{n}}=(-1{)}^n{m}^{\underset{‾}{n}}$ and $s(n,k)=(-1{)}^{n-k}c(n,k)$ by definition, this gives $m^{\underset{‾}{n}}={\sum }_{k=0}^{n}s(n,k)m^k$.

A finite linear combination ${\sum }_{j=0}^n{a}_j{m}^{\underset{‾}{j}}$ that vanishes for every $m\in \mathbb{N}$ has all coefficients zero: evaluating at $m=0$ gives $a_0=0$, and after that evaluating at $m=1,2,\dots ,n$ strips off the remaining coefficients triangularly because $m^{\underset{‾}{j}}=0$ for $j>m$ and $m^{\underset{‾}{m}}=m!\mathrm{\ne }0$ by The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$.

Substitute the second-kind expansion of Ordinary powers expand in the falling-factorial basis by the second-kind Stirling numbers into step 1.1. This gives $m^{\underset{‾}{n}}={\sum }_{k=0}^{n}s(n,k){\sum }_{j=0}^{k}S(k,j)m^{\underset{‾}{j}}={\sum }_{j=0}^n({\sum }_{k=j}^{n}s(n,k)S(k,j))m^{\underset{‾}{j}}$.

Apply step 1.2 to the identity of step 2.1. Since the left-hand side is $m^{\underset{‾}{n}}$, the coefficient of $m^{\underset{‾}{j}}$ is ${\delta }_{n,j}$, so ${\sum }_{k=j}^{n}s(n,k)S(k,j)={\delta }_{n,j}$.

The matrix in step 3.1 is lower triangular with diagonal entries $1$, so its inverse is unique. Since step 3.1 shows that $(s(n,k){)}_{n,k\ge 0}$ is a left inverse of $(S(n,k){)}_{n,k\ge 0}$, it is also the right inverse. Hence ${\sum }_{k=j}^{n}S(n,k)s(k,j)={\delta }_{n,j}$ as well.

Steps 3.1 and 4.1 say exactly that the two triangular Stirling matrices are inverse to one another. Therefore the two finite-sum transforms on sequences in any commutative ring are mutually inverse, which is the claimed iff.

In the labelled product on an $n$-label set, choosing the $k$ labels sent to the $\mathcal{A}$-part contributes $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ possibilities, and then one chooses an $\mathcal{A}$-object on those labels and a $\mathcal{B}$-object on the complement. Thus the size-$n$ coefficient is ${\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)a_k{b}_{n-k}$, which is exactly the coefficient rule for the product of exponential generating functions.

For $\mathrm{SEQ}(\mathcal{A})$, a sequence of length $r$ is an $r$-fold labelled product of $\mathcal{A}$ with itself, so its EGF is $A(x{)}^r$. Summing over all $r\ge 0$ gives ${\sum }_{r\ge 0}A(x{)}^r$, and because $A(0)=0$ this formal geometric series equals $1\mathrm{/}(1-A(x))$.

A labelled set of exactly $r$ $\mathcal{A}$-objects is the same data as an ordered $r$-tuple of pairwise disjoint $\mathcal{A}$-objects modulo permutation of the $r$ components. Therefore its EGF is $A(x{)}^r\mathrm{/}r!$, and summing over $r\ge 0$ gives $\exp (A(x))$ by Formal $\exp$ and $\log$ are inverse homomorphisms and formal binomial powers obey the expected addition laws.

A labelled cycle of exactly $r\ge 1$ $\mathcal{A}$-objects has $r$ linear representatives, so its EGF is $A(x{)}^r\mathrm{/}r$. Summing over $r\ge 1$ gives ${\sum }_{r\ge 1}A(x{)}^r\mathrm{/}r=\log (1\mathrm{/}(1-A(x)))$ by Formal $\exp$ and $\log$ are inverse homomorphisms and formal binomial powers obey the expected addition laws.

In a boxed product, the smallest label lies in the $\mathcal{A}$-part. On size-$n$ labels this is equivalent to choosing a pointed $\mathcal{A}$-object on some $k\ge 1$ labels, with the distinguished label forced to be the smallest, and then a $\mathcal{B}$-object on the remaining labels. Pointing contributes the derivative $A^{\mathrm{\prime }}(x)$, so the derivative of the boxed-product EGF is $A^{\mathrm{\prime }}(x)B(x)$. Since no boxed product has size $0$, the constant term is $0$, and integrating from $0$ to $x$ gives the displayed formula.

Steps 1.1-3.1 are exactly the labelled symbolic-method rules claimed in the statement.

A partition of $[n]$ into exactly $k$ blocks is a labelled set of exactly $k$ nonempty labelled sets. The EGF of a nonempty labelled set of atoms is $e^x-1$, and taking an unordered set of exactly $k$ such blocks contributes the factor $1\mathrm{/}k!$. Therefore ${\sum }_{n\ge 0}S(n,k)\frac{x^n}{n!}=\frac{(e^x-1{)}^k}{k!}\mathrm{.}$

A permutation with exactly $k$ cycles is a labelled set of exactly $k$ labelled cycles of atoms. The EGF of one labelled cycle is $\log (1\mathrm{/}(1-x))$, so the same labelled-set rule gives ${\sum }_{n\ge 0}c(n,k)\frac{x^n}{n!}=\frac{1}{k!}{(\log \frac{1}{1-x})}^k\mathrm{.}$

Steps 1.1 and 1.2 are exactly the two claimed vertical exponential generating functions.

A set partition is a labelled set of nonempty labelled sets. Marking each block by a factor of $u$ replaces the basic block EGF $e^x-1$ by $u(e^x-1)$. Applying the labelled-set rule therefore gives ${\sum }_{n\ge 0}{\sum }_{k=0}^{n}S(n,k)u^k\frac{x^n}{n!}=\exp \text{\hspace{0.17em}⁣}(u(e^x-1))\mathrm{.}$

Setting $u=1$ sums over all block counts and therefore replaces ${\sum }_{k=0}^{n}S(n,k)$ by $B_n$. This yields ${\sum }_{n\ge 0}{B}_n{x}^n\mathrm{/}n!=\exp (e^x-1)$.

Steps 1.1 and 2.1 prove the refined formula and its Bell-number specialization.

For a fixed $k\le n$, [F2] and the change of index $m=\mathrm{\ell }-k$ give. [F2, F3, algebra] ${\sum }_{\mathrm{\ell }\ge 0}\frac{{\mathrm{\ell }}^{\underset{‾}{k}}}{\mathrm{\ell }!}={\sum }_{\mathrm{\ell }\ge k}\frac{1}{(\mathrm{\ell }-k)!}={\sum }_{m\ge 0}\frac{1}{m!}=e\mathrm{.}$ In particular each of these nonnegative series converges.

Substitute [F1] into the series in the Statement. Since the sum over $k$. [F1, F4, step 1.1, algebra] is finite, it may be interchanged with the convergent nonnegative series, and step 1.1 yields ${\sum }_{\mathrm{\ell }\ge 0}\frac{{\mathrm{\ell }}^n}{\mathrm{\ell }!}={\sum }_{k=0}^{n}S(n,k){\sum }_{\mathrm{\ell }\ge 0}\frac{{\mathrm{\ell }}^{\underset{‾}{k}}}{\mathrm{\ell }!}=e{\sum }_{k=0}^{n}S(n,k)=e{B}_n\mathrm{.}$

Multiplying step 2.1 by $e^{-1}$ and using [F3] gives. [F3, step 2.1, algebra] $B_n=e^{-1}{\sum }_{\mathrm{\ell }\ge 0}\frac{{\mathrm{\ell }}^n}{\mathrm{\ell }!}\mathrm{.}$ This also covers $n=0$, where $0^0=1$ is the natural-power base convention already used in [F1].

An involution is a labelled set of fixed points and transpositions, so its EGF is $\exp (x+x^2\mathrm{/}2)$.

An ordered Bell structure is a sequence of nonempty labelled sets. The EGF of one nonempty labelled set is $e^x-1$, so the sequence rule gives $1\mathrm{/}(1-(e^x-1))=1\mathrm{/}(2-e^x)$.

A partition with no singleton blocks is a labelled set of blocks of size at least $2$. Subtracting the singleton contribution $x$ from the basic block EGF $e^x-1$ leaves $e^x-1-x$, and the set rule gives $\exp (e^x-1-x)$.

These are exactly the three claimed specializations.

Fix $n\ge 1$ and $k\in \{1,\dots ,n\}$. Take a permutation of $[n]$, written as a word of length $n$, and choose $k-1$ of the $n-1$ gaps between consecutive letters. Cutting the word at those gaps produces an ordered list of $k$ nonempty ordered blocks. This gives $n!\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)$ ordered lists of ordered blocks.

Forgetting the left-to-right order of the $k$ blocks divides by $k!$, because every unordered family of $k$ internally ordered blocks has exactly $k!$ linear orders of its blocks. Hence $L(n,k)$ counts partitions of $[n]$ into $k$ nonempty linearly ordered blocks.

For $m\in \mathbb{N}$, consider $m$ distinguishable boxes arranged from left to right. Building an ordered list inside each box by inserting the elements $1,2,\dots ,n$ one after another gives $m(m+1)\cdots (m+n-1)=m^{\bar{n}}$ possibilities. Grouping the outcomes by the number $k$ of nonempty boxes, one first chooses the underlying partition of $[n]$ into $k$ internally ordered blocks, counted by $L(n,k)$ from step 2.1, and then chooses the $k$ occupied boxes in order, which gives $m^{\underset{‾}{k}}$ possibilities. Summing over $k$ yields $m^{\bar{n}}={\sum }_{k=0}^{n}L(n,k)m^{\underset{‾}{k}}$.

Steps 2.1 and 3.1 prove the counting interpretation and the falling-factorial expansion on natural arguments, together with the defining value $L(0,0)=1$.

Let $\sigma$ act on the set of partitions of $[n+p]$ by relabelling the elements $n+1,\dots ,n+p$. Every orbit has size $1$ or $p$, because $\sigma$ has prime order $p$. Therefore the total number $B_{n+p}$ is congruent modulo $p$ to the number of fixed partitions.

Let $\mathcal{P}$ be fixed by $\sigma$. By [L1], $\sigma$ permutes the blocks of $\mathcal{P}$. If one block of $\mathcal{P}$ contains one of the last $p$ elements and also some element of $[n]$, then $\sigma$ fixes that element of $[n]$ and cycles the last $p$ elements transitively, so that block must contain all of $n+1,\dots ,n+p$. If instead a block containing one of the last $p$ elements is disjoint from $[n]$, then its $\sigma$-orbit consists of pairwise disjoint blocks of the same size. Because there are exactly $p$ moved elements and $p$ is prime, this leaves only two possibilities: either all $p$ moved elements are singleton blocks, or they all lie in one block. In the singleton case the remaining $n$ elements may be partitioned arbitrarily, giving $B_n$ fixed partitions. In the one-block case the last $p$ elements lie in one block together with some subset $S\subseteq [n]$; choosing the complement $T:=[n]\setminus S$ and partitioning $T$ arbitrarily is exactly the construction counted in The Bell numbers satisfy $B_{n+1}={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)B_k$, so this case contributes $B_{n+1}$ fixed partitions.

Every fixed partition is of one of those two types, and each nonfixed orbit has cardinality divisible by $p$. Hence $B_{n+p}\equiv B_n+B_{n+1}(\mathrm{m}\mathrm{o}\mathrm{d}p)$.