Prove that $\sum_{k = r}^{n} k(k - 1)(k - 2)\cdots(k - r+ 1)D_n(k) = n!$

Question

Prove that $$\sum_{k = r}^{n} k(k - 1)(k - 2)\cdots(k - r+ 1)D_n(k) = n!$$ where $D_n(k)$ represents the number of permutations of length $n$ with exactly $k$ fixed points.

Hello, I am trying this problem.

We can re-arrange the LHS to look like $$\sum_{k=r}^{n}\binom{k}{r}r!D_n(k)$$ Now, the combinatorial approach becomes apparent:

This is just counting the number of pairs of type $$(\text{ordered array of length }r, \text{Permutations where these } r \text{ points are fixed points})$$

Another way to count this is by first picking the array in $\binom{n}{r}r!$ ways, and then multiplying this with the number of permutations where these $r$ points are fixed points: $(n -r)!$. So, total = $$\binom{n}{r}r!(n-r)! = n!$$

I am also looking for algebraic approach. Does anybody have any idea how to algebraically prove this?

Thanks.

Answer 1

\begin{align} \sum_{k=r}^n \frac{k!}{(k-r)!}D_n(k) &= \sum_{k=r}^n\frac{k!}{(k-r)!}\binom nk(n-k)!\sum_{i=0}^{n-k}{(-1)^i\over i!} \\&= n!\sum_{k=r}^n\sum_{i=0}^{n-k}\frac{(-1)^i}{(k-r)!\cdot i!} \\&= n!\sum_{k=0}^{n-r}\sum_{i=0}^{n-r-k} \frac{1}{k!}{(-1)^i\over i!} \end{align} The double summation $\sum_{k=0}^{n-r}\sum_{i=0}^{n-r-k} $ effectively ranges over all ordered pairs $(k,i)$ in the discrete triangle $\{(k,i)\in \mathbb N\times \mathbb N\mid k+i\le n-r\}$, where we first sum over columns, and then take the sum of the column sums. Instead, we could equivalently sum over each diagonal, and take the sum of the diagonal sums. Using this idea, last summation can be rewritten as $$ n!\sum_{d=0}^{n-r}\sum_{i=0}^{d}\frac{(-1)^i}{i!(d-i)!} $$ Really, we are reindexing by defining $d=k+i$. We conclude by noting $$ \sum_{i=0}^{d}\frac{(-1)^i}{i!(d-i)!}=\frac{1}{d!}\sum_{i=0}^d(-1)^i\binom di= \begin{cases} 1 & d=0\\ 0 & d > 0 \end{cases} $$ which of course follows from the binomial theorem, $(1-1)^d=\sum_{i=0}^d \binom di (-1)^i$.

Answer 2

Using combinatorial classes we have the following class $\mathcal{P}$ of permutations with fixed points marked:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \textsc{SET}( \mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \textsc{CYC}_{=2}(\mathcal{Z}) + \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

This gives the EGF

$$F(z, u) = \exp\left(uz+\frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \cdots \right) \\ = \exp\left(\log\frac{1}{1-z} + (u-1)z\right) = \frac{1}{1-z} \exp\left((u-1)z\right) \\ = \frac{1}{1-z} \exp\left(-z\right) \exp\left(uz\right).$$

Hence permutations with exactly $k$ fixed points have EGF

$$G(z) = \frac{z^k}{k!} \frac{\exp(-z)}{1-z}.$$

We thus obtain for our sum

$$n! [z^n] \sum_{k=r}^n {k\choose r} r! \frac{z^k}{k!} \frac{\exp(-z)}{1-z} \\ = n! [z^n] \frac{\exp(-z)}{1-z} \sum_{k\ge r} \frac{1}{(k-r)!} z^k.$$

Here we have extended to infinity due to the coefficient extractor. Continuing,

$$n! [z^n] \frac{\exp(-z)}{1-z} z^r \sum_{k\ge r} \frac{1}{(k-r)!} z^{k-r} \\ = n! [z^n] \frac{z^r}{1-z}.$$

We have $r\le n$ so we may write

$$n! [z^{n-r}] \frac{1}{1-z} = n!$$

as claimed.