Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that we have:

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

share|improve this question
1  
Very similar to mathoverflow.net/questions/83344/… ... –  Daniel Freedman Dec 14 '11 at 1:20
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? –  Gerry Myerson Dec 14 '11 at 1:49
2  
Maybe I could help if the humongous font weren't yelling at me. –  Quinn Culver Dec 14 '11 at 1:56
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. –  Gerry Myerson Dec 14 '11 at 2:05
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 illegible –  user16299 Dec 14 '11 at 3:07

3 Answers 3

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$.

share|improve this answer

$$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}$$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.