14
$\begingroup$

I have to prove that:

$$\frac{(k!)!}{k!^{(k-1)!}} \in \Bbb Z$$

for any $k \geq 1, k \in \Bbb N$

Tried doing $t = k!$ which would give $$\frac{t!}{t^{t/k}}$$

But I think I just made it harder, and I have no other clue!

$\endgroup$
11
$\begingroup$

A hint:

Assume that there are $(k-1)!$ colors, and that you have $k$ balls of each color. In how many ways can you arrange them in a long line?

$\endgroup$
  • $\begingroup$ (+1) I love the combinatorial approach (probably because I'm bad at it; I often just resort to prime factorisations). $\endgroup$ – Lord_Farin Apr 10 '13 at 12:31
  • $\begingroup$ @Lord_Farin: I first tried to do this by counting the multiplicity of each and every prime. It is surprisingly close, so the trial lower bound was not quite good enough. I think it is possible to do it that way, but one has to exercise some care. $\endgroup$ – Jyrki Lahtonen Apr 10 '13 at 12:40
  • $\begingroup$ In my opinion it is enough to say this for a proof. I mean, out of the logic of combinatorics, the number of options of sorting something is a final Integer. Thank you. $\endgroup$ – TheNotMe Apr 10 '13 at 13:18
6
$\begingroup$

We have $$(n!)!=\prod_{i=1}^{n!}i=\prod_{k=1}^{(n-1)!}u_{n,k}$$where$$u_{n,k}=\prod_{i=kn-n+1}^{kn}i=(kn-n+1)\cdots(kn)=n!{kn\choose{n}}$$ hence $$(n!)!=(n!)^{(n-1)!}\left(\prod_{k=1}^{(n-1)!}{kn\choose n}\right)$$

$\endgroup$
5
$\begingroup$

The multinomial coefficient $$ {n\choose k_1,k_2,\ldots, k_r}, $$ where all the variables are non-negative integers and $k_1+k_2+\cdots+k_r=n$, counts the number of ways we can partition a set of $n$ objects into subsets $A_1,A_2,\ldots,A_r$ such that $|A_i|=k_i$ for each $i$. Alternatively it is the coefficient of the term $x_1^{k_1}x_2^{k_2}\cdots x_r^{k_r}$ in the multinomial expansion of $(x_1+x_2+\cdots+x_r)^n$.

It is easy to show by induction on $r$ (using the more common binomial coefficient as the base case as well as the inductive step) that $$ {n\choose k_1,k_2,\ldots, k_r}=\frac{n!}{k_1!k_2!\cdots k_r!}. $$

The number in the question is the multinomial coefficient with $n=k!$, $r=(k-1)!$ and $k_i=k$ for all $i=1,2,\ldots,(k-1)!$.

Therefore it is an integer.

$\endgroup$
  • $\begingroup$ But then, $n=k!$ so $k! \cdot (k-1)! \neq n$, hence $\sum k_i \neq n$. $\endgroup$ – Jean-Claude Arbaut Apr 10 '13 at 12:31
  • $\begingroup$ @arbautjc: But $k \cdot (k-1)! = n$. The $k_i$ are all equal to $k$, not $k!$. $\endgroup$ – Clive Newstead Apr 10 '13 at 12:33
  • $\begingroup$ There was a typo in the first version, where I had "one factorial sign too many", and the $k_i$ marked equal to $k!$. They are supposed to be equal to $k$. Some people of course saw the version, where the misprint was still there. $\endgroup$ – Jyrki Lahtonen Apr 10 '13 at 12:37
  • $\begingroup$ Ok, now everything is ok. Clive's comment made me think I had misread. $\endgroup$ – Jean-Claude Arbaut Apr 10 '13 at 12:39

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.