50
$\begingroup$

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.

$\endgroup$
0

12 Answers 12

70
$\begingroup$

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.

$\endgroup$
2
  • 9
    $\begingroup$ 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. $\endgroup$
    – kjo
    Feb 1, 2014 at 21:05
  • 2
    $\begingroup$ @BillDubuque Neat! (+1) As a layperson, shall I refer to this as the 'Dubuque method of shifts' in my notebook? :} $\endgroup$ Sep 18, 2020 at 22:50
61
$\begingroup$

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

$\endgroup$
4
  • 8
    $\begingroup$ Among many nice answers, I like this one the best. $\endgroup$ Aug 11, 2010 at 20:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – user21820
    Dec 1, 2014 at 10:03
  • 3
    $\begingroup$ @QiaochuYuan Can you please help me how to use the lemma to prove your proposed question. I have also asked it here. $\endgroup$
    – Henry
    Dec 14, 2015 at 9:43
  • $\begingroup$ @QiaochuYuan Thanks, I really like your answer. $\endgroup$ Jan 21 at 12:37
22
$\begingroup$

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.

$\endgroup$
0
19
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – Andrew
    Aug 11, 2010 at 17:24
  • 1
    $\begingroup$ Is that because given n (or more) consecutive integers one of them will always be divisible by n? $\endgroup$ Aug 13, 2010 at 13:05
19
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ 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... $\endgroup$ Aug 11, 2010 at 16:19
  • 22
    $\begingroup$ @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)!}$.) $\endgroup$ Aug 11, 2010 at 17:37
18
$\begingroup$

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!}$$

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 11, 2010 at 17:42
11
$\begingroup$

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$$

$\endgroup$
0
11
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Let's prove using induction, the special case of two numbers, i.e., the statement that if $p, q$ $\in \mathbb{N}$ then $p!q!|(p+q)!$.

(Assume any new variables introduced below to refer to natural numbers.)

First note that since $(p+1)! = (p+1)p!1!$, the statement is true for $q = 1$ and any $p$ (including $p = 1$). In particular, it is true for $p + q = 1 + 1 = 2$. Let us assume that the statement holds for $p, q$ such that $p + q = n$.

Now, for $p, q$ such that $p + q = n + 1$, we can write $$(p + q)! = (p + q)(p + q - 1)!$$ $$= p [\underbrace{(p - 1) + q}_n]! + q [\underbrace{p + (q - 1)}_n]!$$ $$= p \underbrace{k_1 (p-1)!q!}_{\text{using induction assumption}} + q \underbrace{k_2 p!(q-1)!}_{\text{using induction assumption}}$$ $$= (k_1 + k_2) p! q!$$. Hence the principle of mathematical induction implies the truth of the statement.

Now it is easy to prove the analogous statement for three numbers, i.e. $p!q!r! | (p + q + r)!$, since (using the statement just proven) $(p + q + r)!$ is divisible by $p! (q+r)!$ and $(q + r)!$ is divisible by $q!r!$.

This can be generalised for any number of parts, by induction.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .