# Derangements, Dobiński's formula, and their combination

A couple of years ago, someone on a mailing list asked for a proof for their observation that

$$B_n = \sum_{k=1}^{n} \frac{k^n}{k!}\cdot\frac{!(n-k)}{(n-k)!}$$

where $B_n$ denotes the Bell numbers (the number of set partitions of $n$ items), and $$!(n-k)$$ aka $D_{n-k}$ denotes the number of derangements of $n-k$ items.

Actually, this appears to be the $m=n$ special case of something more general: whenever $m \le n$, we can say

$$B_m n! = \sum_{k} {n \choose k} k^m D_{n-k}$$

The “symbolic method” of Flajolet and Sedgewick (from their book Analytic Combinatorics) gives a nice unifying framework that puts in perspective (1) the relation between permutations and derangements, (2) Dobinski’s formula, and (3) this result — when viewed from this lens, all these results feel very natural (IMO).

## 0. Background (EGFs and labelled products)

Suppose we have a combinatorial class $$\mathcal{C}$$, i.e. a set of objects such that $$C_n$$ is the number of objects of size $$n$$ and is finite. Then the exponential generating function (EGF) of this class is defined as

$C(z) = \sum_{n} C_n \frac{z^n}{n!}$

It makes sense to use EGFs when these objects are labelled, i.e. if an object is of size $$n$$, then it contains $$n$$ elements that have labels $$1, 2, \ldots, n$$. For example, $$\mathcal{C}$$ may be the class of all permutations, so that $$C_n$$ counts the number of permutations of $$n$$ items.

Some trivial examples:

• $$\mathcal{E}$$ for the classes containing only a single element of size 0, thus having EGF $$E(z) = 1$$.

• $$\mathcal{Z}$$ for the class containing only a single element of size $$1$$, thus having EGF $$Z(z) = z$$.

• $$\mathcal{U} = \operatorname{S\scriptsize ET}(\mathcal{Z})$$ for an “urn”, i.e. a set of elements: There is exactly one for every size, i.e. $$U_n = 1$$ for all $$n$$, and $$U(z) = \sum_{n} {z^n \over n!} = e^z$$.

We can define the labelled product of two such combinatorial classes: put together an object from the first class and an object from the second, redistributing labels so that the relative order is consistent within each object. For two classes $$\mathcal{A}$$ and $$\mathcal{B}$$, this operation, denoted $$\mathcal{A} \star \mathcal{B}$$, corresponds to the product of the EGFs.

Note that the binomial convolution $$C_n = \sum_{k} {n \choose k} A_k B_{n-k}$$ corresponds to both

• the combinatorial interpretation (to obtain an object of size $$n$$ in $$\mathcal{C} = \mathcal{A} \star \mathcal{B}$$, take an object of size $$k$$ from $$\mathcal{A}$$, and one of size $$n-k$$ from $$\mathcal{B}$$, choose in $$n \choose k$$ ways which $$k$$ labels of $$n$$ are given to the former, and re-label both accordingly), and

• the formal expression: the coefficient of $$z^n$$ in $$C(z) = A(z)B(z)$$, namely $$[z^n]C(z) = C_n/n!$$ is got via products of the form $$A_k {z^k \over k!} B_{n-k} {z^{n-k} \over (n-k)!} = {1 \over n!} {n \choose k} A_k B_{n-k} z^n$$ for some $$k$$.

With that quick background (explained more clearly in the book!), all three results have very short proofs.

$\def\stirling#1#2{\left\lbrace{#1 \atop #2}\right\rbrace}$

## 1. Permutations and derangements

Let $$\mathcal{P}$$ be the class of all permutations. There are $$P_n = n!$$ permutations of size $$n$$, so its EGF is $$P(z) = \sum_n P_n \frac{z^n}{n!} = \sum_{n} z^n = \frac{1}{1-z}$$. (In fact we can also obtain this by noting that any permutation is either the empty permutation or the labelled product of a single element and a smaller permutation, so $$\mathcal{P} = \mathcal{E} + \mathcal{Z} \star \mathcal{P}$$ which for the EGF gives $$P(z) = 1 + zP(z)$$ or $$P(z) = \frac{1}{1-z}$$.)

Let $$\mathcal{D}$$ be the class of all derangements. Then note that any permutation is the labelled product of a derangement and a set of elements (the fixed points). So

$\mathcal{P} = \mathcal{D} \star \mathcal{U}$

$P(z) = D(z) e^z$

Comparing coefficients of $z^n/n!$ gives the relation $$n! = \sum_{k} \binom{n}{k} D_k$$, or equivalently, from $$D(z) = e^{-z}P(z)$$, the relation $$D_n = \sum_k \binom{n}{k} (-1)^k (n-k)! = n! \sum_k \binom{n}{k} \frac{1}{k!}$$

(BTW, the same “symbolic method” also gives us a couple of other ways of deriving the same expression for $D_n$; see this Math.SE answer.)

## 2. Surjections and all functions (Dobiński’s formula)

Fix a set $$S$$ of size $$M$$ for some fixed constant integer $$M$$. (For example, $$S$$ may be $$\{1, 2, \ldots, M\}$$.)

Let $$\mathcal{R}$$ be the class of all surjective (“onto”) functions from $$S$$ to some prefix of the natural numbers. That is, $$R_n$$ counts the number of surjective functions from $$S$$ to $$\{1, 2, \ldots, n\}$$. This is an ordered set partition, so the number is $$R_n = n!\stirling{M}{n}$$, where the notation $\stirling{M}{n}$ denotes the number of partitions of a set of size $M$ into $n$ parts, known as the Stirling subset numbers (aka Stirling numbers of the second kind). We can see this as: partition $$S$$ into $$n$$ nonempty subsets (the preimage of each element), then order these $$n$$ subsets in any of $$n!$$ ways. (Note that $$R_n$$ is $$0$$ for $$n > M$$.)

Let $$\mathcal{F}$$ be the class of all functions from $$S$$ to some prefix of the natural numbers. That is, $$F_n$$ counts the number of functions from $$S$$ to $$\{1, 2, \ldots, n\}$$, and this of course is $$n^M$$.

Now, any such function is the labelled product of a surjection and set of “dummy” elements (in the co-domain but not in the range). So we have

$\mathcal{F} = \mathcal{U} \star \mathcal{R}$

$F(z) = e^z R(z)$

Setting $$z = 1$$ here gives

$\sum_{n} \frac{n^M}{n!} = e \sum_{n} n! \stirling{M}{n} \frac{1}{n!} = e \sum_{n} \stirling{M}{n} = eB_M$

which is known as Dobiński’s formula.

I had posted this online at some point, excuse the handwriting: ## 3. Putting them together

Above we’ve seen that $$\mathcal{P} = \mathcal{U} \star \mathcal{D}$$ and that $$\mathcal{F} = \mathcal{U} \star \mathcal{R}$$. Putting them together, we have

$\mathcal{F} \star \mathcal{D} = \mathcal{R} \star \mathcal{U} \star \mathcal{D} = \mathcal{R} \star \mathcal{P}$

$F(z) D(z) = R(z) P(z)$

So

\begin{align} \sum_{k} {n \choose k} k^M D_{n-k} &= \sum_{k} {n \choose k} k!\stirling{M}{k} (n-k)! \\\
&= n! \sum_{k \le n} \stirling{M}{k} \end{align}

and for $$n \ge M$$ the RHS is $$n! B_M$$. This is precisely the identity we initially wanted to prove.