Combinatoric proof of an algebric expression How can we prove that $\left(\frac{n}{k}\right)^k\le \binom{n}{k}$
I try with induction but I don't get the result I want.
 A: I'm going to assume that $k \neq 0$, thus $k\geq 1$
$\left(\frac{n}{k}\right)^k = \underbrace{\frac{n}{k}\frac{n}{k}\cdots \frac{n}{k}}_{\text{k-terms}}$
$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}$ from which $\frac{n-i}{k-i} \geq \frac{n}{k}$ for $0 \leq i \leq k-1$.
It's unclear whether you need a combinatorial proof or not, induction doesn't constitute a combinatorial proof, and combinatorial proofs tend to verify that two different ways of counting things are equal, but you have an inequality. In any case here is a direct proof.
A: First multiply both sides by $k^k$.
$$n^k \le {n \choose k}k^k$$
Then the new $RHS$ gives you the number of ways in which you select $k$ out of $n$ people and hand them $k$ balls one by one, with no restriction to the number one man can receive. $n^k$ gives you the number of ways to hand $k$ balls to $n$ people without the restrictions.
But note that whenever you included person $A$ on the $RHS$, you counted the situation of him receiving all the $k$ balls all those times, in every combination of $k$ people in which he was included. On the $LHS$ you counted this situation only once. Similarly for any number of balls. Thus the $RHS$ is always greater than $LHS$, unless $k=1$ when you have equality, and you get the reason why.
