Prueba combinatoria de la desigualdad de los números de Stirling

Question

Aquí hay una bonita desigualdad para los números de Stirling sin signo del primer tipo: $$\genfrac[]{0pt}{}{n}{n-k}\leq\frac{n^{2k}}{2^kk!}.$$ Puedo demostrarlo usando la inducción (con una hermosa aplicación de AM-GM, ver más abajo), pero ¿hay una prueba combinatoria?

---

Aquí está el núcleo de la prueba de inducción: $$\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*}$$ donde la última desigualdad (el penúltimo paso) utiliza la desigualdad AM-GM. Me parece realmente hermoso cómo la desigualdad AM-GM funciona perfectamente aquí sin necesidad de otras estimaciones.

Answer 1

Aquí hay una prueba diferente con poco, si es que hay algún sabor combinatorio: de Concrete Mathematics, 2nd Ed. (Ecuación 6.44) tenemos $$ {n \brack n-k} = \sum_{j\ge 0} \bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg> { n+j\choose 2k},$$ donde los enteros no negativos $\bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>$ son los números eulerianos de segundo orden, que satisfacen (Ecuación 6.42, ibid.) $$ \sum_{j \ge 0} \bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>= \frac{(2k)!}{2^k k!}.$$ Pero en realidad, excepto cuando $k=0$ y $j=0$ donde $\bigg<\bigg<\begin{array}{c}0\\0\end{array}\bigg>\bigg>=1 $ el número euleriano de segundo orden $\bigg<\bigg<\begin{array}{c}k\\j\end{array}\bigg>\bigg>=0 $ para $ j \ge k$ . Véase la interpretación combinatoria del número euleriano de segundo orden, en el mismo libro.

La [in]igualdad en el caso $k=0$ es trivial, y entonces consideramos el caso $k>0$ . Entonces, el índice en la suma puede estar limitado por $j<k$ y $n+j \ge 2k$ y entonces tenemos $$\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*} $$ y luego $$ {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!} .$$