Proving $\sum_{k=m}^n \binom{k}{m} {n\brack k} = \sum_{k=m}^n \frac{n!}{k!} {k\brack m} $

Question

the following two identities involve (unsigned) Stirling numbers of the first kind: $$ \sum_{k=m}^n \binom{k}{m} {n\brack k} =_{(1)} {n+1\brack m+1} =_{(2)} \sum_{k=m}^n \frac{n!}{k!} {k\brack m} $$ 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 ${n\brack k}$.

taking coefficients of $x^{m+1}$ in the identity $ P_{n+1}(x)=xP_n(x+1) $ : $$ \begin{align} {n+1\brack m+1}&=[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 {n\brack k} (x+1)^k \\ \\ &= \sum_{k=m}^n \binom{k}{m} {n\brack k} \end{align} \\ $$ (b) to interpret (2) combinatorially we use the fact that ${n\brack k}$ is the number of ways of placing $n$ objects in $k$ cycles.

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

then we may equate the RHS to ${n+1\brack m+1}$ 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.

Answer 1

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 ${n\brack k}$), pick any $m$ of the $k$ cycles (which can be done in $\binom{k}{m}$ 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 ${n+1\brack m+1}$. 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).

Answer 2

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

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{CYC}(\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].$$

Answer 3

A slightly less well known combinatorial interpretation of the unsigned Stirling number of the first kind is the number of permutations of $\{1,\dots,n\}$ with $k$ left-to-right maxima.

A left-to-right maximum of a permutation $\pi$ of $\{1,\dots,n\}$ is a position $i$ such that $\pi(j)<\pi(i)$ for all $j<i$. In particular, $n$ is always the value of the rightmost left-to-right maximum, and $1$ is always the position of the leftmost left-to-right maximum.

Identity (1) says that the number of permutations of $\{1,\dots,n\}$ with at least $m$ left-to-right maxima, $m$ of which are chosen as "special", is equal to the number of permutations of $\{1,\dots,n+1\}$ with exactly $m+1$ left-to-right maxima.

Here is a bijection between the two classes of permutations.

Let $\pi$ be a permutation of $\{1,\dots,n\}$, and suppose its $k\ge m$ left-to-right maxima are in positions $1=i_1<\dots<i_k\le n$. Note that $\pi(i_1)<\dots<\pi(i_k)=n$. Set $i_{k+1}=n+1$, and define the subblocks $$ \pi_{j}=\pi(i_j)\dots\pi(i_{j+1}-1), \quad i=1,\dots,k. $$ Then $\pi$ is the concatenation of subblocks $\pi_j$, $j=1,\dots,k$, i.e. $\pi=\pi_1\dots\pi_k$.

Choose $m$ left-to-right-maxima $i_{j_1}<\dots<i_{j_m}$ and declare them "special". Let $\pi'$ be the string $\pi$ with subblocks $\pi_{j_1},\dots,\pi_{j_m}$ deleted. Then our map $f$ is $$ \pi=\pi_1\dots\pi_k\mapsto f(\pi)=\pi_{j_1}\dots\pi_{j_m},n+1,\pi'. $$ In other words, we partition $\pi$ into maximal blocks starting on the left with each successive left-to-right minimum, choose $m$ of those blocks, then arrange them in their order from left to right, followed by $n+1$, followed by the rest of the blocks in their original order. Thus, all "special" blocks go on the left of $n+1$, and all "nonspecial" blocks go on the right of $n+1$.

The inverse of this map is as follows: mark the blocks before $n+1$ as "special", partition the string $\pi'$ to the right of $n+1$ into maximal blocks starting with the left-to-right minima of $\pi'$, then remove $n+1$ and arrange all the blocks (to the left and to the right of $n+1$) in the increasing order of their left-to-right minima.

For example, $\color{red}{21}\|43\|\color{red}{65}\|87\longleftrightarrow\color{red}{21}\|\color{red}{65}\|\mathbf{9}|43|87$. Here $n=8$, $m=2$, $k=4$.