15
$\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$
0

3 Answers 3

13
$\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$
3
  • $\begingroup$ (+1) I love the combinatorial approach (probably because I'm bad at it; I often just resort to prime factorisations). $\endgroup$
    – Lord_Farin
    Commented Apr 10, 2013 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$ Commented Apr 10, 2013 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
    Commented Apr 10, 2013 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$
0
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$
4
  • $\begingroup$ But then, $n=k!$ so $k! \cdot (k-1)! \neq n$, hence $\sum k_i \neq n$. $\endgroup$ Commented Apr 10, 2013 at 12:31
  • $\begingroup$ @arbautjc: But $k \cdot (k-1)! = n$. The $k_i$ are all equal to $k$, not $k!$. $\endgroup$ Commented Apr 10, 2013 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$ Commented Apr 10, 2013 at 12:37
  • $\begingroup$ Ok, now everything is ok. Clive's comment made me think I had misread. $\endgroup$ Commented Apr 10, 2013 at 12:39

You must log in to answer this question.

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