1
$\begingroup$

Show that we have:

$ \binom{n}{s}\leq n^n $

  • 0
    -1: for intentionally and repeatedly mutilating the question.2012-01-06

3 Answers 3

5

Any coefficient in line $n$ of Pascal triangle is at most the sum $2^n$ of the line. This proves your inequality for every $n\geqslant2$ since then $2^n\leqslant n^n$.

Or:

Note that $\displaystyle{n\choose s}=\frac1{s!}\prod\limits_{k=0}^{s-1}(n-k)\leqslant \frac1{s!}n^s\leqslant n^s$. This proves your inequality for every $n\geqslant s$ since then, $n^s\leqslant n^n$. If $n\lt s$, $\displaystyle{n\choose s}=0$ hence the proof is complete for every positive $n$ and $s$.

3

Here's a more explicitly combinatorial answer. If $s > n$ then the inequality holds because $\binom{n}{s}=0$. If $s \leq n$ note that $\binom{n}{s}s!$ counts the number of injective functions from a set of $s$ elements to a set of $n$ elements. Clearly, that's less than the number of all functions from a set of $n$ elements to another set of $n$ elements, and there are $n^n$ such functions. Since we have $\binom{n}{s}\leq\binom{n}{s}s!$ and $\binom{n}{s}s!\leq n^n$, the desired inequality holds.

2

$n^n=(s+(n-s))^n = \sum_{i=0}^n \binom{n}{i}s^i(n-s)^{n-i}\ge \binom{n}{s}s^s(n-s)^{n-s}\ge \binom{n}{s}$