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.
Best Answer
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!} .$$