Stirling numbers of the second kind vs. binomial coefficient

Question

For $n,k$ positive integers, such that $n\geq k$, denote by $\left\{{n\atop k}\right\} $ the Stirling numbers of the second kind and $\binom{n}{k}$ the binomial coefficient. It is rather straightforward to prove that $\left\{{n\atop k}\right\} \geq \binom{n}{k}$.

According to some calculation it looks like we also have $n^k\left\{{n\atop k}\right\} \geq k^n\binom{n}{k}$.

I tried to prove this via induction using $\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}$, but no luck. Any idea?

Answer 1

Here is an induction proof.

First notice that $$\tag 1 n^k\left\{{n\atop k}\right\} \geq k^n\binom{n}{k}$$ is true for any $n$ when $k=1$ and for any $k$ when $n=k$ , in which cases both sides are equal actually.

Let $n\ge 1$ and $n \ge p\ge 1$. The induction hypothesis is that $ m^k\left\{{m\atop k}\right\} \geq k^m\binom{m}{k}$ is true (for all $k$) for all $m \le n$ and that $ (n+1)^k\left\{{n+1\atop k}\right\} \geq k^{n+1}\binom{n+1}{k}$ is true for all $k \le p$.

A well-known generalised recursion for the Stirling numbers of the second kind is $$ {n+1 \brace p+1}=\sum_{m=p}^n {n \choose m}{m \brace p} $$ Then $$ {n+1 \brace p+1}\ge \sum_{m=p}^n {n \choose m}\frac{p^m}{m^p}{m \choose p}={n \choose p}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$ that is $$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{p+1}{n+1}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$ $$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{(p+1)^{n+1}}{(n+1)^{p+1}}\frac{(n+1)^{p}}{(p+1)^{n}}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} $$

whence $$ {n+1 \brace p+1}\ge {n+1 \choose p+1}\frac{(p+1)^{n+1}}{(n+1)^{p+1}} $$ since $$\frac{(n+1)^{p}}{(p+1)^{n}}\sum_{m=p}^n\frac{p^m}{m^p} {n-p \choose n-m} \ge 1$$ as is shown here.

Answer 2

Notice that $$k^n\binom{n}{k}=\sum _{j=1}^k\binom{n}{j}{n\brace j}j!\binom{n-j}{k-j},$$ this can be shown by realizing that the LHS counts the number of functions from $[n]$ to $[n]$ with image size less or equal than $k$ (say surjective on $j$ elements.) and you complete the image by choosing $k-j$ elements outside the image.

Also, we can use that $x^k = \sum _j {k\brace j}x^{\underline{j}}$to see $$n^k{n\brace k}=\sum _{j=1}^k\binom{n}{j}j!{k \brace j}{n\brace k}.$$ Your inequality is then a consequence of $${n\brace k}{k\brace j}\geq {n\brace j}\binom{n-j}{k-j}.$$ This last inequality can be checked by considering the following (The description is modulo bijections, for example in between $\binom{[n]}{k}$ and $\binom{X}{k}$ for $|X|=n$ so careful reading) function $$f:{[n]\brace k}\times {[k]\brace j}\longrightarrow {[n]\brace j}\times \binom{[n-j]}{k-j},$$ defined by $f(\pi _1=\{A_1,\cdots,A_k\},\pi _2=\{B_1,\cdots,B_j\})=(\pi,X)$ with $$\pi = \left \{\bigcup _{x\in B}A_x:B\in \pi _2\right \},\, X = Min(\pi _2)\setminus Min(\pi),$$ where $Min(\pi):= \text{Set of minimum elements of each block in }\pi.$

This function is surjective, consider $(\pi, X)$ with $X\cap Min( \pi)=\emptyset$ and $|X|=k-j$ then just take $$\pi _1 =\{B\setminus X: B\in \pi \}\cup \{\{x\}:x\in X\}$$ and $$\pi _2 = \{\{ a\}\cup\{x\in X:\text{x and a are in a block in }\pi\}:a\in Min(\pi)\}.$$ Check that $f(\pi _1,\pi _2)=(\pi,X).$