TITLE: Show that $(k!)!$ is divisible by $(k!)^{(k-1)!}$
QUESTION [3 upvotes]: Question : Show that $(k!)!$ is divisible by $(k!)^{(k-1)!}$.
Answer : Suppose we've $k!$ objects, where k objects of 1st kind, k objects of 2nd kind,...k objects of $(k-1)!$ kind (why?). And from the well known formula we get :
$$ \frac{(k!)!}{k!k!...k!((k-1) times)**(why?)**} = \frac{(k!)!}{(k!)^{(k-1)!}}$$
My question is from where we do we get the idea of having $(k-1)$ in the calculation. I'm confused. Please help me.

REPLY [2 votes]: Let $\lfloor r\rfloor$ denote the floor of $r$ 
(i.e. the largest integer $\leq r)$.
Lemma 1 
For $a \in \Bbb{R}_{\geq 0}, ~b\in \Bbb{Z^+}, ~
b\lfloor a\rfloor \leq \lfloor ab\rfloor.$
Proof: 
Let $a = P + r,~~$ where $P \in \Bbb{Z}_{\geq 0}, ~~0 \leq r < 1.$ 
Thus, $P = \lfloor a\rfloor$. 
Further, $(ba) - ( bP) = (br).$ 
Let $c = \lfloor (br) \rfloor \implies 0 \leq c.$
Then, $\lfloor (ba) \rfloor = (bP) + c \implies 
\lfloor (ba) \rfloor \geq (bP) = b\lfloor a\rfloor.$

Given two positive integers, $a,b$, you can show that $\frac{a}{b}$ is an integer by showing that for any prime $p$, if $p^r$ is in the prime factorization of $b$, then $p^s$ is in the prime factorization of $a$, where $s \geq r.$
Use Legendre formula:
$$v_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac{n}{p^k}\right\rfloor.$$
In order to show that $(k!)^{(k-1)!}$ divides $[(k!)!]$, it is sufficient to show that for any prime $p$, if $d$ is the largest non-negative integer such that $p^d$ divides $(k!)$, then $p^{d(k-1)!}$ divides $[(k!)!].$
So, by assumption:
$$
\left\lfloor \frac{k}{p^1}\right\rfloor ~+~ 
\left\lfloor \frac{k}{p^2}\right\rfloor ~+~ 
\left\lfloor \frac{k}{p^3}\right\rfloor ~+~ 
\cdots = d.\tag1$$
It is sufficient to prove that :
$$
\left\lfloor \frac{k!}{p^1}\right\rfloor ~+~ 
\left\lfloor \frac{k!}{p^2}\right\rfloor ~+~ 
\left\lfloor \frac{k!}{p^3}\right\rfloor ~+~ 
\cdots \geq d(k-1)!.\tag1$$
However, this result is immediate, by invoking Lemma 1, term by term.
That is:
$$\left\lfloor \frac{k}{p^1}\right\rfloor \times (k-1)! \leq 
\left\lfloor \frac{k!}{p^1}\right\rfloor.$$
$$\left\lfloor \frac{k}{p^2}\right\rfloor \times (k-1)! \leq 
\left\lfloor \frac{k!}{p^2}\right\rfloor.$$
$$\left\lfloor \frac{k}{p^3}\right\rfloor \times (k-1)! \leq 
\left\lfloor \frac{k!}{p^3}\right\rfloor.$$
$$\cdots$$
{"set_name": "stack_exchange", "score": 3, "question_id": 4177811}