1
$\begingroup$

Show that we have:

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

  • 1
    Very similar to http://mathoverflow.net/questions/83344/an-inequality-from-an-erdos-paper ...2011-12-14
  • 4
    It should not be up to readers here and at MO to alert people to posts at other sites - **you** should have done that when you first posted the questions. Can you not make any use of the estimate given in one of the comments at MO?2011-12-14
  • 0
    @GerryMyerson I believe Bob may be the asker on MO, and has come here to ask a simpler version of the same question2011-12-14
  • 2
    Maybe I could help if the humongous font weren't yelling at me.2011-12-14
  • 0
    I rearranged one factor so that the inequality is more readable. Hope it's ok.2011-12-14
  • 2
    @DevenWare, yes, I was operating on that assumption, and my point stands: when you post the same question, or two versions of a question, or two closely related questions, on two different sites, you are obliged to include a link to the other site at both places.2011-12-14
  • 0
    @GerryMyerson Yes, I think I misread, misunderstood the complaint. My apologies.2011-12-14
  • 2
    Quinn: the humongous font is my fault, due to an edit I made at MO, because some of us decrepit folk find LaTeX's defaults for nested expressions just a **bit** illegible2011-12-14
  • 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}$$