$(n^2 - 1)!$ is a multiple of $(n!)^n$

Question: Find all positive integers $n$ such that $(n^2 - 1)!$ is a multiple of $(n!)^n$.

I can show that the required condition fails if $n$ is a prime, and by direct computation, it also fails for $n=4$. After doing a few small examples by hand, I believe that the required answer is 1 and all composites greater than 4. However, I cannot seem to prove this.

For each prime $p<n$, I tried to count the number of appearances of $p$ on both sides, but I get that I am supposed to compare $n(\lfloor{\frac{n}{p}} \rfloor + \lfloor{\frac{n}{p^2}} \rfloor +\dots)$ against $\lfloor{\frac{n^2-1}{p}} \rfloor + \lfloor{\frac{n^2-1}{p^2}} \rfloor + \dots$, which is not obvious to compare.

Any help will be gretaly appreciated.

Solution 1:

Suppose you have $n^2$ objects of $n$ colours so that each colour occurs exactly $n$ times. In how many colour patterns can you arrange these objects in a line? Answer by standard combinatorics: $$A=\frac{n^2!}{n!n!\cdots n!}=\frac{n^2!}{n!^n}$$ (We can arrange the objects in $n^2!$ ways, but within each colour group, we identify the $n!$ possible orders). This is of course an integer.

If we go further and allow the colours to be permuted (i.e., we identify arrangements that show the same pattern, but with differetn overall colour assignments), we count $$ B=\frac A{n!}=\frac{n^2!}{n!^{n+1}}$$ and that is still an integer.

Our questions asks, when $$C:=\frac A{n^2}=B\cdot \frac{n!}{n^2}$$ is an integer. This is certainly the case whenever $n^2$ divides $n!$, i.e., whenever $n$ divides $(n-1)!$. This finally is the case when $n$ is the product of two distinct integers $<n$, so for all composites except prime squares.

But even if $n=p^2$ with $p>2$, we have $p$ and $2p$ among the factors defining $(n-1)!$ and therefore $n$ again divides $(n-1)!$.

This shows that $C$ is an integer for all composite $\ne 4$. As you already treated the cases $n=1$, $n=4$, and prime $n$, this completes the result.