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.

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|improve this question
12  
@Andrew: Then why mention it? :-) –  ShreevatsaR Aug 11 '10 at 17:43
    
@ShreevatsaR I apologise if it was spam. It was just to show that there is yet another way of proving it, and I may return to this page after publication. –  Andrew Aug 11 '10 at 17:58
2  
So @Andrew, were you really intending to post your proof here? –  J. M. Oct 29 '11 at 11:05

8 Answers 8

up vote 9 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|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|improve this answer
4  
Among many nice answers, I like this one the best. –  Pete L. Clark Aug 11 '10 at 20:17

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$

$$\frac{}{1}\frac{}{2}\frac{}{3}\frac{}{4}\frac{}{5}\frac{}{6}\frac{23}{7}\frac{24}{8}\frac{25}{9}\frac{26}{10}\frac{27}{11}\frac{28}{12}\frac{29}{13}\frac{30}{14}\frac{31}{15}\frac{32}{16}\frac{33}{17}\frac{34}{}\frac{35}{}\frac{36}{}\frac{37}{}\frac{38}{}\frac{39}{}$$

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|improve this answer
1  
Very elegant idea! –  Andres Caicedo Nov 9 '10 at 5:24
    
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 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|improve this answer
2  
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
13  
@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|improve this answer
    
I wanted to indent the equality, but the simplest standard TeX spacing "\ \ \ \ " didn't work. –  wlod Aug 11 '10 at 15:48
    
use two dollars for centered LaTeX, (single dollar for inline). [; \cdots ;] doesn't work on this site.... –  anon Aug 11 '10 at 15:58
    
We use dollar signs to denote TeX equations like $this$. –  KennyTM Aug 11 '10 at 15:58
1  
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|improve this answer
    
This is an overkill (I don't even attempt to read it :-). –  wlod Oct 14 '13 at 21:57
1  
@wlod: That takes some skill, judging overkill without even reading it :-) –  Aryabhata Oct 15 '13 at 8:47
1  
Call it intuition. –  wlod Mar 10 at 8:48
    
@wlod: :-)...... –  Aryabhata Mar 11 at 8:11

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|improve this answer
4  
This is implicitly what wlod's answer does, with an example. –  ShreevatsaR Aug 13 '10 at 16:57

Please look at this link: http://mathdl.maa.org/images/upload_library/22/Hasse/00029890.di021346.02p0064l.pdf

share|improve this answer
    
Can't see this link, is it correct? –  Guillermo Phillips Aug 11 '10 at 15:41
    
The correct link is mathdl.maa.org/images/upload_library/22/Hasse/… –  anon Aug 11 '10 at 15:47

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.