How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$? How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?
I can only manage to see the second inequality, could any one give a hint about the first one?
 A: $$\binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n(n - 1)\cdots (n - k + 1)}{k (k - 1) \cdots 1} = \frac{n}{k}\frac{n - 1}{k - 1} \cdots \frac{n - (k - 1)}{1}\geq \frac{n}{k} \cdots \frac{n}{k} = \left(\frac{n}{k}\right)^k$$
where we used the inequality that for $i$ such that $1 \leq i \leq k - 1$,
$$\frac{n - i}{k - i} \geq \frac{n}{k}$$
which is easy to verify.
A: Combinatorial Proof:
Denote by $[n]$ the set $\{1,2,\ldots,n\}$ and $\binom{[n]}{k}$ is the set of all subsets of $[n]$ with $k$ elements.  Let $$A:=\Big\{\left(S,x_1,x_2,\ldots,x_k\right)\in \binom{[n]}{k}\times\mathbb{Z}^k\,\Big|\,x_i\in S\text{ for every }i\Big\}$$ and $$B:=\Big\{\left(x_1,x_2,\ldots,x_k\right)\in\mathbb{Z}^k\,\Big|\,1\leq x_i\leq n\text{ for every }i\Big\}\,.$$  The map $f:A\to B$ sending $\left(S,x_1,x_2,\ldots,x_k\right)\mapsto\left(x_1,x_2,\ldots,x_k\right)$ is a surjection.  Thence,  $|A|\geq |B|$.  However, $|A|=\binom{n}{k}\cdot k^k$ and $|B|=n^k$.  Hence, $\binom{n}{k}\cdot k^k \geq n^k$, or $\left(\frac{n}{k}\right)^k\leq\binom{n}{k}$.
Now, $\binom{n}{k}\cdot k!$ is the number of ways to arrange $k$ objects from a collection of $n$ distinct objects on a line without repetition.  On the other hand, $n^k$ is the number of ways to arrange $k$ objects from a collection of $n$ distinct objects on a line where repetition is allowed.  Clearly, $\binom{n}{k}\cdot k! \leq n^k$.  Thus, $\binom{n}{k}\leq \frac{n^k}{k!}$.
A: It is easy to prove $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$ if we write it as $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\\ \frac{n(n-1)}{k(k-1)}\binom{n-2}{k-2}=\\\frac{n(n-1)(n-2)}{k(k-1)(k-2)}\binom{n-3}{k-3}=\\..\\\frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\binom{n-k}{k-k}=\\ \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\binom{n-k}{0}\\=\frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))} $$so $$\frac{n}{k}\frac{n}{k}...\frac{n}{k}\leq \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\leq\frac{n(n)(n)...(n)}{k(k-1)(k-2)...(k-(k-1)))}\\ \frac{n^k}{k^k}\leq \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\leq \frac{n^k}{k!} $$
