Combinatorial Proof of Stirling Number Inequality 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.
 A: 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!} .$$
A: 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. $$
A: 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}.$$
