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.
Best Answer
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 $\rm (mod\ 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$ 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 $\,\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.