How to prove that $(p^2)!$ is divisible by $(p!)^{p+1}$?

Question

For each prime $p$, find the greatest natural power of $p!$, which divides the number $(p^2)!$ ($n!=1 \cdot 2 \cdot ...\cdot n$)

My work so far:

1) $p=2 \Rightarrow p!=2; (p!)^2=4!=24 \vdots 8=2^3$. Answer: $3=2+1$

2) $p=3 \Rightarrow p!=6; (p!)^2=9!=362880 \vdots 1296=6^4$. Answer: $4=3+1$

Hypothesis: The answer is $p+1$.

If $(p^2)!$ divided by $(p!)^n, n \in \mathbb N$, then $n \le p+1$.

How to prove that $(p^2)!$ is divisible by $(p!)^{p+1}$ ?

Answer 1

Here is a combinatorial proof of $(n!)^{n+1} \mid (n^2)!$:

Suppose we have $n^2$ people, that we will divide in $n$ teams of $n$ people. If we first consider each place to be unique, then we get $(n^2)!$. However, in each of the teams we may change the order of the people chosen, so we may divide the number of possibilities by $(n!)^n$. The order in which the teams are chosen also doesn't matter, so we divide by $n!$ again.

This gives a total of $\frac{(n^2)!}{ (n!)^{n+1} }$, possibilities, but the number of possibilities is of course an integer and hence $(n!)^{n+1} \mid (n^2)!$.

Answer 2

it may be helpful to consider a more general result you are likely to be familiar with, namely that $(n+m)!$ is divisible by $n!m!$ (the quotient gives the binomial coefficient). By applying this well-known result repeatedly we show that $(\sum m_k)!$ is divisible by $\prod m_k!$ (the multi nominal coefficient). Now, take each $m_k = p$ and let there be $p$ of them. That will get you as far as having $p!^p$ dividing $(p^2)!$. the missing factor of $p!$ may be connected with the primitivity of p, which we haven't made use of.