How to show $(\frac{n}{m})^m\leq\binom{n}{m}$?

Question

How can I show that $$\left(\frac{n}{m}\right)^m\leq\binom{n}{m},$$where $m \leq n,$ and $m,n \in \Bbb N $?

Answer 1

You can prove this by counting. Write the inequality as:

$$n^m\leq m^m\binom{n}{m}.$$

Notation: We define $[k]=\{1,2,\dots,k\}$ when $k$ is a natural number.

Let $X$ be the set of all pairs $(S,f)$ where $S\subseteq [n]$ has $|S|=m$ and $f$ and any function $[m]: \to S.$

There are $m^m\binom{n}{m}$ elements of $X$.

Let $Y$ be the set of all functions $[m]\to[n].$

There are $n^m$ elements of $Y$.

We define $G:X\to Y$ as:

$$(S,f)\mapsto i_S\circ f$$

where $i_S:S\to [n]$ is the natural inclusion.

To complete the proof, show that $G$ is onto, and thus $|X|\geq |Y|.$

---

Completion of proof:

Take any $g\in Y$, that is any $g:[m]\to [n].$

We know that $\left|\operatorname{im}(g)\right|\leq m,$ since the image of a function has cardinality no bigger than the domain of the function.

Let $S$ be any $m$-element subset of $[n]$ containing $\operatorname{im}(g)$. We define $f:[m]\to S$ as $f(i)=g(i).$ This works because $g(i)\in S.$

Then $G(S,f)=g.$

So $G$ is onto, and $|X|\geq |Y|.$

---

Note, this gives strict inequality if $m\neq 0,1,n.$ (For $m=0$, we take $0^0=1,$ which is the natural "combinatorial" value for $0^0.$

If $m>1$ and $m<n$ then we can take $g:[m]\to [n]$ as any constant function. Then there are $\binom{n-1}{m-1}$ choices for $S$.

Now, $\binom{n-1}{m-1}\leq 1$ precisely when $m=0,1,n.$

So there are multiple values of $S$ we can choose, and hence $|X|>|Y|.$

Answer 2

$$\binom{n}{m} = \frac{n}{m} \frac{n-1}{m-1} \cdots \frac{n-m+2}{2} \frac{n-m+1}{1} \overset{?}{\ge} \underbrace{\frac{n}{m} \frac{n}{m} \cdots \frac{n}{m} \frac{n}{m}}_{m}.$$

Answer 3

By the definition we have

$$\left(\frac{n}{m}\right)^m\leq\binom{n}{m} \iff \frac{n^m}{m^m}\le \frac{n!}{m!(n-m)!}$$

$$\iff \frac{n\cdot n\cdot \ldots\cdot n}{m\cdot m\cdot \ldots\cdot m}\le \frac{n(n-1)\ldots(n-m+1)}{m(m-1)\ldots1}$$

then note

$$\frac n m \le \frac{n-k}{m-k} \iff nm-kn\le nm-km \iff m\le n$$