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!
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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?
answered Apr 10, 2013 at 12:23
-
$\begingroup$ (+1) I love the combinatorial approach (probably because I'm bad at it; I often just resort to prime factorisations). $\endgroup$ 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$ 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$– TheNotMeApr 10, 2013 at 13:18
$\begingroup$
$\endgroup$
0
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)$$
$\begingroup$
$\endgroup$
4
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.
answered Apr 10, 2013 at 12:27
-
$\begingroup$ But then, $n=k!$ so $k! \cdot (k-1)! \neq n$, hence $\sum k_i \neq n$. $\endgroup$ 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$ 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$ Apr 10, 2013 at 12:37
-
$\begingroup$ Ok, now everything is ok. Clive's comment made me think I had misread. $\endgroup$ Apr 10, 2013 at 12:39