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

I have a partition of a positive integer $(p)$. How can I prove that the factorial of $p$ can always be divided by the product of the factorials of the parts?

As a quick example $\frac{9!}{(2!3!4!)} = 1260$ (no remainder), where $9=2+3+4$.

I can nearly see it by looking at factors, but I can't see a way to guarantee it.

share|cite|improve this question

11 Answers 11

up vote 10 down vote accepted

The key observation is that the product of $n$ consecutive integers is divisible by $n!$. This can be proved by induction.

share|cite|improve this answer
A quicker proof than induction would be to note that (by definition) $\binom{k}{n}$ is an integer, hence $n!|k\cdot (k-1)\ldots (k-n+2)\cdot (k-n+1)$. – Andrew Aug 11 '10 at 17:24
Is that because given n (or more) consecutive integers one of them will always be divisible by n? – Guillermo Phillips Aug 13 '10 at 13:05

The "high-level" way to see this is to recall that whenever a finite group $G$ has a subgroup $H$, we know that $|H|$ divides $|G|$. Then note that $S_n$ clearly contains $S_{n_1} \times ... \times S_{n_k}$ as a subgroup for any partition $n_1 + ... + n_k = n$. (This is actually the same as the combinatorial interpretation in Robin Chapman's answer, since what we are counting is the number of cosets $G/H$, and these cosets are precisely what the multinomial theorem is counting.)

This basic lemma is surprisingly useful. For example, it is not hard to use it to show that $m! (n!)^m$ divides $(mn)!$.

share|cite|improve this answer
Among many nice answers, I like this one the best. – Pete L. Clark Aug 11 '10 at 20:17
Hmm it's also not hard to see that $\frac{(mn)!}{m!(n!)^m}$ is the number of ways of putting $mn$ distinct objects into $m$ groups, since the number of ways to permute the groups is $m!$ and the number of ways of permuting within every group is $(n!)^m$. Any not so trivial usage of that lemma? – user21820 Dec 1 '14 at 10:03
@QiaochuYuan Can you please help me how to use the lemma to prove your proposed question. I have also asked it here. – Henry Dec 14 '15 at 9:43

Below is a sketch of a little-known purely arithmetical proof that binomial coefficients are integral. I purposely constructed the proof so that it would be comprehensible to an educated layperson. The proof gives an algorithm to rewrite a binomial coefficient as a product of fractions whose denominators are coprime to any given prime. The method of proof is best comprehended by applying the algorithm to a specific example.
[Note: It may prove helpful to first read this simpler example before proceeding to the exposition below].

E.g. consider $\ \ \binom{39}{17}\: =\: \frac{39!}{22! \; 17!}\: =\: \frac{23 \cdot 24 \cdots\; 39}{1 \cdot 2 \cdots\; 17}\:.\ $ When this fraction is reduced to lowest terms $\rm\:a/b\:,\ $ no prime $\rm\ p > 17\ $ can divide its denominator $\rm\: b\:,\: $ since $\rm\ b\:|\:17\:!\ \:$ Hence, to show that $\rm\ a/b\ $ is an integer, it suffices to show that no prime $\rm\ p \le 17\ $ divides its denominator $\rm\: b\:$.

E.g. we show that $2$ doesn't divide $\rm b$. The highest power of $2$ in the denominator terms is $16 < 17$. Now align the numerator and denominator terms $\rm (mod\ 16)$ by shifting the 1st numerator term so it lies above its value $\rm (mod\ 16)$, viz. $23 \equiv 7 \pmod{16}$ so right-shift the numerator terms until $23\:$ lies above $7$


Now I claim that $2$ doesn't divide the reduced denominator of each aligned fraction. Indeed $\ 24/8 = 3$, $\: 26/10 = 13/5 $, $\:\ 28/12 = 7/3 $, $\:\ 30/14 = 15/7 $, $\:\ 32/16 = 2$. This holds because these fractions $\rm\; c/d \;$ satisfy $\rm c \equiv d\ (mod\ 16)\:$ i.e. $\rm c = d + 16\: n \;$ so $\rm 2|d \Rightarrow 2|c$, $\rm\; 4|d \Rightarrow 4|c$, $\:\cdots $, $\rm\; 16|d \Rightarrow 16|c$, i.e. any power of $2\:$ below $16$ that divides $\rm d$ must also divide $\rm c$, so it cancels out upon reduction.

Therefore to prove that $2$ doesn't divide the reduced denominator of $\binom{39}{17}$ it suffices to prove the same for the "leftover" fraction composed of the above non-aligned terms $(34 \cdots 39)/(1 \cdots 6) = \binom{39}{6}$. Being an $\rm\binom{n}{k}$ with smaller $\rm k = 6 < 17\:,\:$ this follows by induction.

Since the same proof works for any prime $\rm p$, we conclude that no prime divides the reduced denominator of $\binom{39}{17}$, therefore it is an integer.$\quad$ QED

Informally, the reason that this works is because the denominator sequence starts at $1$, which is coprime to every prime $\rm p$. This ensures that it is the "greediest" possible contiguous sequence of integers, in the sense that its product contains the least power of $\rm\:p\:$ compared to other contiguous sequences of equal length.

The algorithm extends to multinomials by using the simple reduction of multinomials to products of binomials mentioned in my prior post here.

share|cite|improve this answer
As elegant as it is, this proof strikes me as requiring more mathematical sophistication than does the standard combinatorial proof of $\binom{n}{k}\in\mathbb{N}$. This makes me wonder how many "purely arithmetic" proofs of divisibility in number theory can be reduced to simpler combinatorial arguments. – kjo Feb 1 '14 at 21:05

These quotients are integers since they solve counting problems. For instance, how many nine-letter words are there with 2 As, 3 Bs and 4 Cs?

For the full story see the multinomial theorem.

share|cite|improve this answer
While true, it's not a good answer - usually one needs to be convinced that the quotients are integers before they can understand why the results are the solution to a counting problem... – BlueRaja - Danny Pflughoeft Aug 11 '10 at 16:19
@BlueRaja: Not at all! Showing that some ratio is the solution to a counting problem is my favourite way of proving divisibility. You don't need to be convinced that the quotient is an integer here; once you show it's the number of [something], it has to be an integer. (You don't usually check divisibility and compare prime factors when you show that the number of ways of choosing k out of n is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.) – ShreevatsaR Aug 11 '10 at 17:37

If you believe (:-) in the two-part Newton case, then the rest is easily obtained by induction. For instance (to motivate you to write a full proof):

$$\frac{9!}{2! \cdot 3! \cdot 4!}\ =\ \frac{9!}{5!\cdot 4!}\cdot \frac{5!}{2!\cdot 3!}$$

share|cite|improve this answer
In terms of multinomial coefficients: choosing (2, 3, and 4) out of 9 is the same as first choosing 4 from the original 9, then choosing 2 and 3 out of the remaining 5. Etc. – ShreevatsaR Aug 11 '10 at 17:42

Here is another proof:

We use Legendre's formula for the exact power of a prime $p$ which divides $n!$ which is given by

$$ \sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$

where $\lfloor x\rfloor$ is the integer part of $x$.

Coupled with $$ \sum_{i=1}^{n} \left\lfloor x_i\right\rfloor \le \left\lfloor\sum_{i=1}^{n} x_i \right\rfloor$$

we get that if $\sum_{i=1}^{n} a_i = N$ then

$$\sum_{i=1}^{n} \left\lfloor\frac{a_i}{p^k}\right\rfloor \le \left\lfloor\frac{N}{p^k}\right\rfloor $$

And so any prime power which divides $(a_1)! \dots (a_n)!$ divides $N!$ and so $\displaystyle \frac{N!}{(a_1)! \dots (a_n)!}$ is an integer.

share|cite|improve this answer

Besides the obvious combinatorial interpretations, one also has the has the following reduction from multinomial coefficient to products of binomial coefficients. Namely for $n = i+j+k+\cdots + m $

$$ \frac{n!}{i!j!k!\cdots m!} = \binom{n}{i} \frac{(n-i)!}{j!k!\cdots m!} = \binom{n}{i}\binom{n-i}{j} \frac{(n-i-j)!}{k!\cdots m!} = \;\cdots$$

share|cite|improve this answer

$$\frac{(x+y+z)!}{x!y!z!} = \binom{x + y + z}{x + y} \binom{x + y}{x}.$$

share|cite|improve this answer

To show that $\frac{(x+y+z)!}{x!y!z!}$ is an integer (when $x$, $y$, and $z$ are non-negative integers) it is enough to show that $\frac{(x+y+z)!}{x!y!z!}$ counts something.

Consider all words of length $x+y+z$ made up of $x$ occurrences of the letter A, $y$ occurrences of the letter B, and $z$ occurrences of the letter C. There are $\frac{(x+y+z)!}{x!y!z!}$ such words.

share|cite|improve this answer

Hint. Write $$\eqalign{(x+y+z)! &=[(1)(2)\cdots(x)]\cr &\qquad{}\times[(x+1)(x+2)\cdots(x+y)]\cr &\qquad{}\times[(x+y+1)(x+y+2)\cdots(x+y+z)]\cr}$$ and use a well-known fact about a product of $n$ consecutive integers.

share|cite|improve this answer

The number of powers of $p$ dividing $n!$ is $\sum_{k=1}^n \lfloor \frac{n}{p^k} \rfloor$, and we have $\lfloor \frac{x+y+z}{q} \rfloor \geq \lfloor \frac{x}{q} \rfloor + \lfloor \frac{y}{q} \rfloor + \lfloor \frac{z}{q} \rfloor$.

share|cite|improve this answer

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.