11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ – marcelolpjunior Nov 22 '13 at 10:33
  • $\begingroup$ Nice solution.......marcelolpjunior.. $\endgroup$ – juantheron Nov 22 '13 at 18:09
5
$\begingroup$

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

[My original backwards answer follows.]

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.

$\endgroup$
10
  • $\begingroup$ 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!$? $\endgroup$ – Patrick Nov 21 '13 at 18:19
  • $\begingroup$ 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) $\endgroup$ – robjohn Nov 21 '13 at 18:28
  • 3
    $\begingroup$ @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}}} $$ $\endgroup$ – robjohn Nov 21 '13 at 18:40
  • $\begingroup$ Duh, of course! $\endgroup$ – Patrick Nov 21 '13 at 19:18
  • $\begingroup$ @Steve Kass I enjoyed your response and your last comment, a certain theorem that I have here in my text fits perfectly, thanks for the reply. :) $\endgroup$ – marcelolpjunior Nov 22 '13 at 10:34
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.