Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that:

(I can't prove without binomial coefficient.)

$$ \big(m+n\big)!\over m!n!$$ is a natural number

you can use : formula for the largest power of a prime dividing a factorial $$ n!=p_1^\alpha* p_2^\beta* ... $$ $$ \alpha= \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor+... $$

share|cite|improve this question
Well, if you use that formula, this boils down to an elementary $\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$. Did you try to prove that? – Alexander Shamov Nov 29 '12 at 15:51
up vote 5 down vote accepted

Let $p$ be a prime. Write $\nu_p(k)$ for the exponent of $p$ in the prime decomposition of $k$. We have for $i \in \mathbb N$: $$ \frac{n+m}{p^i} = \frac n{p^i} + \frac{m}{p^i} $$ so, making the right hand side possibly smaller $$ \frac{n+m}{p^i} \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor $$ Now the right hand side is an integer, hence by definition of the floor function $$ \left\lfloor \frac{n+m}{p^i}\right\rfloor \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor $$ This gives \begin{align*} \nu_p(n!m!) &= \nu_p(n!) + \nu_p(m!)\\ &= \sum_{i=1}^\infty \left\lfloor \frac{n}{p^i} \right\rfloor + \sum_{i=1}^\infty \left\lfloor\frac m{p^i}\right\rfloor\\ &\le \sum_{i=1}^\infty \left\lfloor \frac{n+m}{p^i}\right\rfloor \\ &= \nu_p\bigl((n+m)!\bigr) \end{align*} And therefore $$ n!m! = \prod_p p^{\nu_p(n!m!)} \biggm| \prod_p p^{\nu_p((n+m)!)} = (n+m)! $$ that is the denominator divides the numerator in $\frac{(n+m)!}{n!m!}$ and so the quotient is an integer.

share|cite|improve this answer
form very last equation $n!m! = (n+m)!$ ? – Nikita Evseev Nov 29 '12 at 15:53
Note the $|$ ... it is to be read as "divides", as in $2\mid 4$... – martini Nov 29 '12 at 15:53

Your Answer


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.