Show that $\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}$

Question

Let $m\le n$ be positive integers. I want to prove the inequality $$\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}.$$

I have tried direct algebraic manipulations but they led me nowhere. The $(-1)^{k+m}$ term in the summand seems very annoying. Any ideas on how to handle this sum?

Answer 1

Recall that the Stirling numbers of the second kind ${n\brace k}$ are the number of set partitions of $k$ blocks on $n$ elements. It is a fact of life(inclusion-exclusion principle) that $${n\brace m}=\frac{1}{m!}\sum_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n=\frac{1}{m!}\sum_{k=0}^m(-1)^{m+k}\binom{m}{k}k^n.$$ This means that your inequality is $${n\brace m}\leq \binom{n}{m}m^{n-m}.$$

If you find a way to map one to one a set partition to pairs $(X,f)$ where $|X|=m$ and $f:[n-m]\longrightarrow [m]$, then you would be done.

For the later, consider taking the minimal elements of each block in the partition, call it $X$ and the rest of objects are functions that go from $[n]\setminus X$ to whichever block they belong. This proves your inequality.

Answer 2

In seeking to verify that

$$\sum_{k=0}^m (-1)^{k+m} {m\choose k} \frac{k^n}{m^n} \le {n\choose m} \frac{m!}{m^m}$$

with $m\ge n$ positive integers we first re-write as

$$\sum_{k=0}^m (-1)^{k+m} {m\choose k} k^n \le {n\choose m} m! \times m^{n-m}.$$

The LHS is

$$n! [z^n] \sum_{k=0}^m (-1)^{m-k} {m\choose k} \exp(kz) = n! [z^n] (\exp(z)-1)^m = m! \times {n\brace m}$$

so that we seek with the RHS in falling factorials

$$m! \times {n\brace m} \le n^{\underline{m}} \times m^{n-m}.$$

Now the left side counts partitions of $n$ distinguishable objects into $m$ distinguishable non-empty sets. Imagine a row of $m$ slots into which we distribute $n$ labelled balls so that at the end each slot holds at least one ball. For the right side suppose we seek to enforce the fact that none of the slots are empty by first putting one ball into every one of them. So we choose one of $n$ values for the first slot, leaving $n-1$ choices for the second one, $n-2$ for the third, and so on, for a total of $n^{\underline{m}}$ possibilities. This leaves $n-m$ labeled balls which we distribute any way we like, for $m^{n-m}$ possibilities. In this manner we obtain every sequence of sets (induced by the ordering on the slots) at least once, as any ball from a given slot may serve as a seed value (chosen in the $n^{\underline{m}}$ seed step) for that slot and we have less-than-or-equal inequality.