Combinatorial Proof of Stirling Number Inequality

Question

Here's a cute inequality for unsigned Stirling numbers of the first kind: $$\genfrac[]{0pt}{}{n}{n-k}\leq\frac{n^{2k}}{2^kk!}.$$ I can prove it using induction (with a beautiful application of AM-GM, see below), but is there a combinatorial proof?

---

Here's the core of the induction proof: $$\begin{align*} \genfrac[]{0pt}{}{n}{n-k}&=(n-1)\genfrac[]{0pt}{}{n-1}{n-k}+\genfrac[]{0pt}{}{n-1}{n-k-1}\\ &=(n-1)\genfrac[]{0pt}{}{n-1}{(n-1)-(k-1)}+\genfrac[]{0pt}{}{n-1}{(n-1)-k}\\ &\leq(n-1)\frac{(n-1)^{2(k-1)}}{2^{k-1}(k-1)!}+\frac{(n-1)^{2k}}{2^kk!}\\ &=\frac{1}{2^kk!}(2k+n-1)(n-1)^{2k-1}\\ &\leq\frac{1}{2^kk!}\left(\frac{(2k+n-1)+(2k-1)(n-1)}{2k}\right)^{2k}\\ &=\frac{n^{2k}}{2^kk!} \end{align*}$$ where the last inequality (the penultimate step) uses the AM-GM inequality. I find it really beautiful how the AM-GM inequality works perfectly here with no further estimates needed.

Answer 1

The Stirling number $\genfrac[]{0pt}{}{n}{n-k}$ counts the number of the permutations in the symmetric group $S_n$ which have $n-k$ cycles. Each such a permutation can be written uniquely as a product of transpositions $$ (i_1,j_1) \cdots (i_k,j_k), $$ where $i_1,\dots,i_k,j_1,\dots,j_k\in\{1,\dots,n\}$ are such that (a) $i_1<j_1, \quad i_2<j_2, \quad \dots, \quad i_k<j_k$ and (b) $j_1<\dots<j_k$. In other words, $\genfrac[]{0pt}{}{n}{n-k}$ is equal to the number of the sequences of pairs \begin{equation} \label{eq} (i_1,j_1), \dots, (i_k,j_k) \end{equation} such that the above conditions are fulfilled.

The combinatorial interpretation of the product $\genfrac[]{0pt}{}{n}{n-k} k!$ arises by considering all $k!$ permutations of the above sequence of pairs; in other words is equal to the number of the sequence of pairs \begin{equation} \label{eq2} (i_1,j_1), \dots, (i_k,j_k) \end{equation} such that the condition (a) holds true as before, but now the condition (b) is replaced by the requirement that (b') $j_1,\dots,j_k$ are all different. By dropping the condition (b') it follows that $$ \genfrac[]{0pt}{}{n}{n-k} k! \leq \binom{n}{2}^k. $$

Answer 2

Here is a different proof with little, if any combinatorial flavor: from Concrete Mathematics, 2nd Ed. (Equation 6.44), we have $$ {n \brack n-k} = \sum_{j\ge 0} \bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg> { n+j\choose 2k},$$ where non-negative integers $\bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>$ are the second order Eulerian numbers, satisfying (Equation 6.42, ibid.) $$ \sum_{j \ge 0} \bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>= \frac{(2k)!}{2^k k!}.$$ But actually, except when $k=0$ and $j=0$ where $\bigg<\bigg<\begin{array}{c}0\\0\end{array}\bigg>\bigg>=1 $, the second order Eulerian number $\bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>=0 $ for $ j \ge k$. See the combinatorial interpretation of the second order Eulerian number, in the same book.

The [in]equality in the case $k=0$, is trivial, and then we consider the case $k>0$. Then, the index in the summation may be limited by $j<k$ and $n+j \ge 2k$, and then we have $$\begin {align*} { n+j\choose 2k} &= \frac{(n+j)\cdot \cdot \cdot (n+j-2k+1)}{(2k)!}\\ &\le\frac{(n+k-1)\cdot \cdot \cdot (n-k)}{(2k)!}=\frac{n(n-k)}{(2k)!}\prod_{i=1}^{k-1}(n^2-i^2) \le\frac{n^{2k}}{(2k)!} \end{align*} $$ and then $$ {n \brack n-k} \le \frac{n^{2k}}{(2k)!}\sum_{j \ge 0} \bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg> =\frac{n^{2k}}{2^k k!} .$$

Answer 3

I am not sure if it counts as a combinatorial proof, but at least it avoids induction.

Start with the classical identity for the generating function $$ \sum_{0\leq k \leq n-1} \genfrac[]{0pt}{}{n}{n-k} c^k = (1+c) (1+2c) \cdots \big( 1+(n-1) c \big). $$ Each of the coefficients in each of the factors on the right-hand side is non-negative. Hence the coefficient standing at each monomial $c^k$ can only increase if we increase the coefficients at each factor. Therefore $$ \genfrac[]{0pt}{}{n}{n-k} = [c^k] \bigg[ (1+c) (1+2c) \cdots \big( 1+(n-1) c \big) \bigg] \leq [c^k] \exp c \exp 2c \cdots \exp (n-1)c = [c^k] \exp \frac{n^2 c}{2}.$$