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}$ 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?
 A: 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.
A: 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.
