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.
On
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.
On
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!}$$
On
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$$
On
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)!$.
On
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$. Align the numerators & denominators $\!\bmod 16\,$ by shifting the 1st numerator term so it lies above its value $\!\bmod 16,\,$ viz. $\,\color{#c00}{23 \equiv 7} \pmod{\!16}\,$ so right-shift the numerator terms until $\,23\,$ lies above $\:\!7\,$
$$\color{#0a0}{\frac{}{1}\frac{}{2}\frac{}{3}\frac{}{4}\frac{}{5}\frac{}{6}}\color{#c00}{\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}\color{#0a0}{\frac{34}{}\frac{35}{}\frac{36}{}\frac{37}{}\frac{38}{}\frac{39}{}}$$
We claim that $\,2\,$ does not 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$ dividing $\rm d$ must divide $\rm c$, so it cancels out of $\rm\,c/d$.
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 $\,\color{#0a0}{(34 \cdots 39)/(1 \cdots 6) = \binom{39}{6}}\,$ composed of the above non-aligned terms. 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.
On
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.
The key observation is that the product of $n$ consecutive integers is divisible by $n!$. This can be proved by induction.