# prove that $(n^2)!$ is divisible by $(n!)^{n+1}$, where $n\in \mathbb{N}$

(1) How can we prove that $(kn)!$ is divisible by $(n!)^k$, where $n,k\in \mathbb{N}$

(2) How can we prove that $(n^2)!$ is divisible by $(n!)^{n+1}$, where $n\in \mathbb{N}$

(3) How can we prove that $(k!)!$ is divisible by $(k!)^{(k-1)!}$, where $k\in \mathbb{N}$

$\bf{My\; Try}::(1)$ We know that product of $n$ consecutive integer is divisible by $n!$

So Here $1.2.3.4………………………………….n$ is divisible by $n!$

Similarly $(n+1)\cdot(n+2)\cdot(n+3)………..(2n)$ is divisible by $n!$

Similarly $(2n+1)\cdot (2n+2)\cdot …………..(3n)$ is divisible by $n!$

Similarly $(3n+1)\cdot(3n+2)………………….(4n)$ is divisible by $n!$

…………………………………………………….

…………………………………………………….

Similarly $\{(k-1)n+1\}\cdot \{(k-1)n+2\}\cdot………………\{(k-1)n+n\}$ is divisible by $n!$

So we can say that $(kn)!$ is divisible by $(n!)^k$

Now I did not understand how can i solve $(II)$ one and $(III)$ one

Help Required

Thanks

#### Solutions Collecting From Web of "prove that $(n^2)!$ is divisible by $(n!)^{n+1}$, where $n\in \mathbb{N}$"

$$\frac{(n^2)!}{n!^{n+1}}$$
is the number of paritions of an $n^2$ element set into $n$ (indistinguishable) sets of size $n$ each.

$(3)$ is just a special case of $(1)$ with $k\leftarrow (k-1)!$ and $n\leftarrow k$.

(3) is a direct consequence of (1), as (after a change of name to avoid confusion) $(h!)! = (h(h-1)!)!$ so applying (1) with $n=h$ and $k=(h-1)!$, you get that $(h(h-1)!)!$ is divisible by $(h!)^{(h-1)!}$.

For (2), you have actually that

$$(k+1)n! \mid (kn+1)⋅(kn+2)⋅\dots·((k+1)n)$$

is divisible by $(k+1)n!$, in fact, if you take out the last term, you get

$$(n-1)! \mid (kn+1)⋅(kn+2)⋅\dots·((k+1)n-1)$$

just because it’s the product of $(n-1)$ consecutive integers. Then you multiply by $(k+1)n$ both sides, obtaining that

$$(n-1)!·(k+1)n \mid (kn+1)⋅(kn+2)⋅\dots·((k+1)n-1)·(k+1)n$$

So $n^2!$ can be expressed as a product of

$$\prod_{k=0}^{n-1}\prod_{i=1}^{n}kn+i = \prod_{k=0}^{n-1}P_k$$

And each $P_k$ is divisible by $(k+1)n!$ so the entire product is divisible by

$$\prod_{k=0}^{n-1}(k+1)n! = n!^{n+1}$$

Hint 1: Consider the multinomial coefficient
$$kn \choose n, n,\dots,n$$
that is an integer.

Hint 2: Follow the @Hagen von Eitzen’s method!

Hint 3: Consider the multinomial coefficient
$$k! \choose k,k,\dots,k$$

3 is simple,

plug n = k, m = (k – 1)! into $(mn)!$ is divisible by $(n!)^m$

Going to submit answer to two shortly.

Edit

I am trying to use a proof by induction for 2.

The 0th case (1) is simple $(1^2)! = 1$ and $(1!)^{1+1} = 1$ obviously $1 | 1$ so that case works.

All that needs to be done is to prove that $(n^2)! | (n!)^{n+1} \rightarrow ((n+1)^2)! | ((n+1)!)^{n+2}$