If $p^k|n!$ then $p!^k|n!$

Question

Is there a direct proof of the result that if $p$ is a prime and if $p^k|n!$ then $p!^k|n!$? The proof that I know is rather circuitous (take $k$ to be given by de Polignac's formula and construct a subgroup of $S_n$ of order $p!^k$). The result seems too elegant to not admit a slick combinatorial proof.

Answer 1

Induction on $n$: If $n=mp+r$ with $0\le r<p$, there are $\frac{n!}{p!^mr!m!}$ ways to partitoin $n$ objects into $m$ indistinguishable subsets of size $p$ each and a rest of size $r$. Note that $p^{k-m}\mid m!$ (because the multiples of $p$ among $1,2,\ldots, n$ are precisely $p,2p,,\ldots, mp$) and by induction hypothesis $p!^{k-m}\mid m!$. Hence $p!^n\mid p!^mm!\mid n!$.

Answer 2

I have not been able to show this in general. But in special case

when $k<p$, which will imply $pk \le n$,

So, the no. of of ways of dividing $n$ objects into $k+1$ different boxes such that $k$ boxes contain $p$ objects, while 1 box contain $n-pk$ object is

$\frac{n!}{(p!)^k\times(n-pk)!}$

From here we get that $(p!)^k|n!$

Answer 3

I was talking to some friends about this problem and we came up with a direct proof that (barely) avoids using de Polignac's formula.

For each factor of $p$ in $n!$, we wish to group that factor of $p$ with something divisible by $(p-1)!$. You group the first factor of $p$ dividing a number $x\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. You group the second factor of $p$ dividing a number $px\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. These are precisely what is leftover from the numbers $px-p,px-2p,\ldots,px-(p-1)p$ after the first step. Repeating this process, you group the $(k+1)$-st factor of $p$ dividing a number $p^kx\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. These are precisely what is leftover from the numbers $p^kx-p^k,p^kx-2p^k,\ldots,p^kx-(p-1)p^k$ after $k$th step. However, the binomial coefficient $$\binom{x-1}{p-1}=(x-1)(x-2)\ldots(x-(p-1))/(p-1)!$$ is an integer. This shows that each group is divisible by $p!$. Also, each factor of $p$ in $n!$ is contained in some group and each group contains exactly one factor of $p$. This shows that if $p^k|n!$ then $p!^k|n!$.

This is still not quite the slick combinatorial proof that I was looking for but it's pretty close.