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

January 16, 2023

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 \leq n$ , we can say

$B_{m} n! = \sum_{k} (\binom{n}{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 $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, \dots, n$ . For example, $C$ may be the class of all permutations, so that $C_{n}$ counts the number of permutations of $n$ items.

Some trivial examples:

$E$ for the classes containing only a single element of size 0, thus having EGF $E (z) = 1$ .
$Z$ for the class containing only a single element of size $1$ , thus having EGF $Z (z) = z$ .
$U = S ET (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} \frac{z^{n}}{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 $A$ and $B$ , this operation, denoted $A ⋆ B$ , corresponds to the product of the EGFs.

Note that the binomial convolution $C_{n} = \sum_{k} (\binom{n}{k}) A_{k} B_{n - k}$ corresponds to both

the combinatorial interpretation (to obtain an object of size $n$ in $C = A ⋆ B$ , take an object of size $k$ from $A$ , and one of size $n - k$ from $B$ , choose in $(\binom{n}{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} \frac{z^{k}}{k!} B_{n - k} \frac{z^{n - k}}{(n - k)!} = \frac{1}{n!} (\binom{n}{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.

1. Permutations and derangements

Let $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 $P = E + Z ⋆ P$ which for the EGF gives $P (z) = 1 + z P (z)$ or $P (z) = \frac{1}{1 - z}$ .)

Let $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

$P = D ⋆ 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, \dots, M}$ .)

Let $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, \dots, n}$ . This is an ordered set partition, so the number is $R_{n} = n! {\binom{M}{n}}$ , where the notation ${\binom{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 $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, \dots, 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

$F = U ⋆ R$

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

Setting $z = 1$ here gives

$\sum_{n} \frac{n^{M}}{n!} = e \sum_{n} n! {\binom{M}{n}} \frac{1}{n!} = e \sum_{n} {\binom{M}{n}} = e B_{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 $P = U ⋆ D$ and that $F = U ⋆ R$ . Putting them together, we have

$F ⋆ D = R ⋆ U ⋆ D = R ⋆ P$

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

$\begin{aligned} \sum_{k} (\binom{n}{k}) k^{M} D_{n - k} & = \sum_{k} (\binom{n}{k}) k! {\binom{M}{k}} (n - k)! \\ = n! \sum_{k \leq n} {\binom{M}{k}} \end{aligned}$

and for $n \geq M$ the RHS is $n! B_{M}$ . This is precisely the identity we initially wanted to prove.