# Proving $\sum_{k=m}^n \binom{k}{m} \begin{bmatrix} n \\ k \end{bmatrix}= \sum_{k=m}^n \frac{n!}{k!} \begin{bmatrix} k \\ m \end{bmatrix}$

the following two identities involve (unsigned) Stirling numbers of the first kind: $$\sum_{k=m}^n \binom{k}{m} \begin{bmatrix} n \\ k \end{bmatrix}=_{(1)} \begin{bmatrix} n+1 \\ m+1 \end{bmatrix} =_{(2)} \sum_{k=m}^n \frac{n!}{k!} \begin{bmatrix} k \\ m \end{bmatrix}$$ the first, (1), has a simple algebraic proof but no obvious combinatorial interpretation, whereas the second, (2), makes sense combinatorially but i have so far found no obvious route to prove it algebraically.

question can anyone provide either or both of these missing links - i.e. an algebraic demonstration of (2) and/or a combinatorial interpretation of (1)? i would also appreciate any perceptive remarks on (i) how it is that combinatorial intuition can sometimes cut through the knot of apparently complex calculations, and (ii) whether there is any formalization which allows proofs to be systematically generated from valid combinatorial arguments.

note

(a) algebraic proof of (1):

let $P_n(x)$ be the polynomial $x(x+1)\dots(x+n-1)$. the coefficient of $x^k$ in $P_n(x)$ is $\begin{bmatrix} n \\ k \end{bmatrix}$.

taking coefficients of $x^{m+1}$ in the identity $P_{n+1}(x)=xP_n(x+1)$ : \begin{align} \begin{bmatrix} n+1 \\ m+1 \end{bmatrix}&=[x^{m+1}]P_{n+1}(x) \\ &=[x^{m+1}]xP_{n}(x+1) \\ &=[x^{m}]P_{n}(x+1) \\ &=[x^{m}]\sum_{k=m}^n \begin{bmatrix} n \\ k \end{bmatrix} (x+1)^k \\ \\ &= \sum_{k=m}^n \binom{k}{m} \begin{bmatrix} n \\ k \end{bmatrix} \end{align} \\ (b) to interpret (2) combinatorially we use the fact that $\begin{bmatrix} n \\ k \end{bmatrix}$ is the number of ways of placing $n$ objects in $k$ cycles.

if we rewrite $$\sum_{k=m}^n \frac{n!}{k!} \begin{bmatrix} k \\ m \end{bmatrix} = \sum_{k=m}^n (n-k)!\binom{n}{k} \begin{bmatrix} k \\ m \end{bmatrix}$$

then we may equate the RHS to $\begin{bmatrix} n+1 \\ m+1 \end{bmatrix}$ by the following argument. to arrange $n+1$ objects as $m+1$ cycles, first set aside any one object. From the remaining $n$ objects, select $j \ge m$. arrange these $j$ objects into $m$ cycles. the $n-j$ unselected objects, together with the object initially set aside, can be arranged as a cycle in $(n-j)!$ ways.

• thanks @Test123! realized something ghastly had happened with the title – David Holden Feb 12 '17 at 18:33

For the second equality recall the conbinatorial species for factorizations into cycles which is

$$\mathfrak{P}(\mathfrak{C}(\mathcal{Z}))$$

which yields

$$\left[k\atop m\right] = k! [z^k] \frac{1}{m!} \left(\log\frac{1}{1-z}\right)^m.$$

This yields for the RHS of identity two

$$\frac{n!}{m!} \sum_{k=m}^n [z^k] \left(\log\frac{1}{1-z}\right)^m = \frac{n!}{m!} [z^n] \frac{1}{1-z} \left(\log\frac{1}{1-z}\right)^m = Q_{n,m}.$$

We also have

$$\sum_{n\ge m+1} \left[n\atop m+1\right] \frac{z^n}{n!} = \frac{1}{(m+1)!} \left(\log\frac{1}{1-z}\right)^{m+1}$$

which implies that (differentiate)

$$\sum_{n\ge m+1} \left[n\atop m+1\right] \frac{z^{n-1}}{(n-1)!} = \frac{1}{m!} \left(\log\frac{1}{1-z}\right)^m \times (1-z) \times \frac{1}{(1-z)^2}$$

or alternatively

$$\sum_{n\ge m} \left[n+1\atop m+1\right] \frac{z^{n}}{n!} = \frac{1}{m!} \frac{1}{1-z} \left(\log\frac{1}{1-z}\right)^m$$

which means that

$$Q_{n,m} = \left[n+1\atop m+1\right].$$

• thanks, great answer. has helped me to understand more about exponential generating functions. – David Holden Feb 13 '17 at 0:58
• Thank you. Both the OGF and the EGF have their respective advantages, here it was the EGF that worked best. – Marko Riedel Feb 13 '17 at 1:01

So here's an idea on how you can prove (1) combinatorially. Let $N$ be the set $\{1 \ldots n\}$, and define $Z = \{(R,B)\}$ where $R$ is a permutation of some subset of $N$ with exactly $m$ cycles (the "red" permutation), and $B$ is any permutation of the remaining elements of $N$ (the "blue" permutation).

On the one hand, for any $k \ge m$, you can start with any permutation of $N$ with $k$ cycles (of which there are $\begin{bmatrix} n \\ k \end{bmatrix}$), pick any $m$ of the $k$ cycles (which can be done in $\left (\begin{matrix} k \\ m \end{matrix}\right)$ ways) to color red, and then the remaining cycles define the blue permutation using cycle notation. This gives the left side of (1).

On the other hand, let $X$ be any permutation of $N \cup \{*\}$, where $*$ is not in $N$, with exactly $m+1$ cycles, of which there are $\begin{bmatrix} n+1 \\ m+1 \end{bmatrix}$. Color the $m$ cycles which do not contain $*$ red.

For the blue permutation, let the remaining cycle $Y$ containing $*$ be written as $(*,y_1, \ldots, y_{\ell})$; since a cycle is identical up to rotation, we may assume without loss of generality that $*$ comes first. Let $\{n_1 \ldots n_\ell\}$ be the elements of $N$ that appear in $Y$, where $n_i < n_{i+1}$; note that as sets $\{y_1 \ldots y_\ell\} = \{n_1 \ldots n_\ell\}$. Define the blue permutation via the function $\pi:n_i \rightarrow y_i$. So every $X$ corresponds to a unique $(R,B)$, showing the right side of (1).

• thanks, very nice. i couldn't see how to make use of the extra element. sorry can't accept your answer as i've already accepted Marko's treatment of the other problem, but +1 anyway! – David Holden Feb 13 '17 at 0:59