Division of Factorials [binomal coefficients are integers]

Solution 1:

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.

Solution 2:

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)!$.