Differentiating the binomial theorem

Question

The standard identity $$ n2^{n-1} = \sum_{k=0}^n k\binom{n}{k} $$ has an easy combinatorial interpretation, which is that both sides count the number of ways to pick a subset of $[n]$ with a marked element. Alternatively, we could look at $$ \frac{d}{dx}(x+1)^n = \frac{d}{dx}\left(\sum_{k=0}^n \binom{n}{k}x^k\right) $$ and then substitute $x=1$ to get the same identity. We can think of this as differentiating moving between counting sets and counting "pointed" sets, which is what we did above without the analytic machinery. This is a specific instance of a fact about generating functions.

If instead we look at $$ \frac{d^n}{dx^n}(e^x - 1) = \frac{d^n}{dx^n}\left( \sum_{k=0}^n\binom{n}{k}(-1)^{n-k}e^{kx} \right) $$ and substitute $x=0$ we get another well-known identity (a special case of the inclusion-exclusion formula for the number of surjections) $$ n! = \sum_{k=1}^n (-1)^{n-k}\binom{n}{k}k^n $$ My question is whether this derivation is an example of a more general technique or has some meaning. I'm not that good at generating functions, so it seems a little mysterious.

Answer 1

Taking the derivative $n$ times and setting $x = 0$ gives you the coefficient of $x^n$ in the exponential generating function:

$$ f(x) = \sum_{k = 0}^\infty f^{(k)}(0) \frac{x^k}{k!}. $$

It is typical to write this as in terms of the coefficient operator $\left[ \frac{x^n}{n!} \right]$ which when applied to a power series $f(x)$ gives you the coefficient of $\frac{x^n}{n!}$ in $f(x)$. In other words

$$\left[ \frac{x^n}{n!} \right] \sum_{k = 0}^\infty a_k \frac{x^k}{k!} = a_n. $$

Then

\begin{align} \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k}k^n &= \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k} \left[ \frac{x^n}{n!} \right] e^{kx} \\ &= \left[ \frac{x^n}{n!} \right]\sum_{k = 0}^n \binom{n}{k} (-1)^{n - k} e^{kx} \\ &= \left[ \frac{x^n}{n!} \right] (e^x - 1)^n. \end{align}

In the theory of combinatorial species, $e^x - 1$ is the (exponential) generating function for non-empty sets. That is, of the map which takes in a set $X$ and spits out the set

$$ \mathcal{E}(X) = \begin{cases} \{X\} & \text{if } X \ne \emptyset \\ \emptyset & \text{if } X = \emptyset \end{cases}. $$

Notice that

$$ |\mathcal{E}(X)| = \begin{cases} 1 & \text{if } X \ne \emptyset \\ 0 & \text{if } X = \emptyset \end{cases} $$

We define the generating function for $\mathcal{E}$ to be

$$ \sum_{n = 0}^\infty |\mathcal{E}([n])| \frac{x^n}{n!} = e^x - 1 $$

where $[n] = \{1, 2, \dots, n\}$.

If $\mathcal{F}$ is a combinatorial species then we define the power $\mathcal{F}^k$ to be the map

$$ \mathcal{F}^k(X) = \bigsqcup_{(S_1,\dots,S_k)} \mathcal{F}(S_1) \times \dots \times \mathcal{F}(S_k) \tag{1}$$

where the union is over all (ordered) partitions of $X$ into $k$ subsets $S_1,\dots,S_k$. That is, $S_1 \cup \dots \cup S_k = X$ and $S_1,\dots,S_k$ are disjoint.

One can show that if $F(x) = \sum_n |\mathcal F([n])| x^n/n!$ is the generating function for $\mathcal{F}$ then $F(x)^k$ is the generating function for $\mathcal{F}^k$.

Bringing this back to $\mathcal{E}^n$ we can say that

$$ \left[ \frac{x^n}{n!} \right] (e^x - 1)^n = |\mathcal{E}^n([n])| $$ is the number of ways of partitioning $[n]$ into $n$-non-empty sets because only the terms in $(1)$ in which $S_1,\dots,S_n$ are all non-empty will contribute to the union.

Partitioning $[n]$ into $n$ singletons is the same thing as a permutation of $n$ and there are $n!$ of these. Hence

$$n! = \left[ \frac{x^n}{n!} \right] (e^x - 1)^n = \sum_{k = 0}^n \binom{n}{k} (-1)^{n - k}k^n. $$