# Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ... Did not come out at all, in fact I could not leave the place, and looked reolhei theorems that shows me the text, but could not solve, need help.

\begin{align} \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} &=\frac{\displaystyle\left(\sum_{i=1}^{n-1}a_i\right)!}{\displaystyle\prod_{i=1}^{n-1}a_i!} \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\left(\sum_{i=1}^{n-1}a_i\right)!\ a_n!}\\ &=\frac{\displaystyle\left(\sum_{i=1}^{n-1}a_i\right)!}{\displaystyle\prod_{i=1}^{n-1}a_i!} \binom{\displaystyle\sum_{i=1}^na_i}{a_n}\\ &=\prod_{k=1}^n\binom{\displaystyle\sum_{i=1}^ka_i}{a_k}\tag{1} \end{align} Thus, the fraction on the left of $(1)$ is a product of binomial coefficients.

We can write $$n!=n(n-1)!=\sum_{i=1}^{(n-1)!}n\tag{2}$$ Using $(2)$ and then $(1)$ \begin{align} \frac{(n!)!}{n!^{(n-1)!}} &=\frac{\displaystyle\left(\sum_{i=1}^{(n-1)!}n\right)!}{\displaystyle\prod_{i=1}^{(n-1)!}n!}\\[4pt] &=\prod_{k=1}^{(n-1)!}\binom{kn}{n}\tag{3} \end{align} Since the right hand side of $(3)$ is a product of binomial coefficients, the left hand side is an integer.

Example

The numbers get huge very quickly, but with $n=4$, $$\frac{(4!)!}{4!^{3!}}=\frac{24!}{24^6}=3,246,670,537,110,000$$ and \begin{align} \prod_{k=1}^{3!}\binom{4k}{4} &=\binom{24}{4}\binom{20}{4}\binom{16}{4}\binom{12}{4}\binom{8}{4}\binom{4}{4}\\[4pt] &=3,246,670,537,110,000 \end{align}

• The statement that you made, is one that I draw attention and make me like it even more math, particularly, found it very beautiful. Thank you! – marcelolpjunior Nov 22 '13 at 10:33
• Nice solution.......marcelolpjunior.. – juantheron Nov 22 '13 at 18:09

[Three years later update] Addressing @Patrick’s comment, I should have said

Suppose you have $(n-1)!$ identical sets of $n$ balls. The balls in each set are numbered 1 through $n$. How many ...

Suppose you have $n$ identical sets of $(n-1)!$ balls. The balls in each set are numbered 1 through $(n-1)!$. How many ways are there to arrange these $n!$ balls in a row? There are $\frac{(n!)!}{(n!)^{(n-1)!}}$ ways.
• Doesn't this argument actually show that $\frac{(n!)!}{\bf{n}^{(n-1)!}}$ is an integer? Since there are $\bf n$ copies of each numbered ball and not $n!$? – Patrick Nov 21 '13 at 18:19
• This is essentially the combinatorial explanation of the product in my answer. The number of ways to place the balls marked $(n-1)!$ is $\binom{n(n-1)!}{n}$. After placing them, there are $\binom{n((n-1)!-1)}{n}$ ways of placing the balls marked $(n-1)!-1$, then $\binom{n((n-1)!-2)}{n}$ of placing the balls marked $(n-1)!-2$, and so on... (+1) – robjohn Nov 21 '13 at 18:28
• @Patrick: this is a standard multinomial coefficient: $$\frac{(n!)!}{n!^{(n-1)!}}=\frac{(\overbrace{n+n+n+\dots+n}^{(n-1)!\text{ terms}})!}{\underbrace{n!\,n!\,n!\dots n!}_{(n-1)!\text{ terms}}}$$ – robjohn Nov 21 '13 at 18:40
This is the same as showing that combinations or binomial coefficients $\displaystyle{n\choose k}=C_n^k=\prod_{j=0}^{k-1}\frac{n-j}{1+j}$ are always natural, for all values of n and k. It all depends on proving that the product of any k consecutive numbers is always divisible through the product of the first k consecutive numbers, $1$ through k. This is obvious, since, in each sequence of $2$ consecutive numbers, exactly one is even, and one odd; in each sequence of three consecutive numbers, exactly one is ternary, while the other two aren't; in each sequence of four consecutive numbers, exactly one is quaternary, while the rest aren't; etc. Our product, $(n!)!=1\cdot2\cdot3\cdot\ldots\cdot n!$, can be broken up into $\displaystyle\frac{n!}n=(n-1)!$ sequences of n consecutive terms, each such sub-product being divisible through n!, for the reasons explained above. In other words, the whole product is divisible through $(n!)^{(n-1)!}$. QED.