Prove quotient of factorials is integral

Question

If $n$ is an integer $\gt 0$, prove

$$\frac{(30n)!n!}{(15n)!(10n)!(6n)!}$$

is also an integer. I understand that a general approach is proving that the power of any prime factor is greater in the numerator than it is in the denominator, but I haven't been able to formulate this into a rigorous proof.

Answer 1

This is a gross brute force answer.

We will show that for any positive integer $D$:

$$0\leq\left\lfloor\frac{30n}{D}\right\rfloor + \left\lfloor\frac{n}{D}\right\rfloor - \left\lfloor\frac{15n}{D}\right\rfloor - \left\lfloor\frac{10n}{D}\right\rfloor - \left\lfloor\frac{6n}{D}\right\rfloor$$

This is enough to show your theorem because when $D=p^k$ is a prime power, this is the total number of multiples of $p^k$ in the numerator minus the total number of multiples of $p^k$ in the denominator.

Write $30n = Dq+r$ for some $0\leq r < D$. Then the right hand side is:

$$q + \left\lfloor\frac{q}{30}\right\rfloor - \left\lfloor\frac{q}{2}\right\rfloor - \left\lfloor\frac{q}{3}\right\rfloor - \left\lfloor\frac{q}{5}\right\rfloor$$

Writing $q=30p+s$ with $0\leq s<30$, we see this is:

$$30p +s + p - 15p -\left\lfloor\frac{s}{2}\right\rfloor - 10p - \left\lfloor\frac{s}{3}\right\rfloor - 6p- \left\lfloor\frac{s}{5}\right\rfloor\\=s-\left\lfloor\frac{s}{2}\right\rfloor - \left\lfloor\frac{s}{3}\right\rfloor - \left\lfloor\frac{s}{5}\right\rfloor$$

If this is non-negative for $s=0,...,29$ you are done. You can brute force from there.

Note

It seems like there should be some direct proof for:

$$0\leq s-\left\lfloor\frac{s}{2}\right\rfloor - \left\lfloor\frac{s}{3}\right\rfloor - \left\lfloor\frac{s}{5}\right\rfloor$$

for $s=0,\dots,29$. However, it is not true for $s=30$.

Answer 2

Here is a short video which shows, among other things, how to compute the highest power of a prime number that will divide a given factorial. Perhaps you could use the method in the video to compute the maximum powers of the common prime factors (2,3,5,7 etc.) in the numerator and the denominator say using $n=1$ as a base case. Then use an inductive step for $n+1$ to develop a proof to show that all the prime factors up to the highest prime factor in the denominator (which will not exceed $kn$ in $kn!$) are also prime factors in the numerator and that the powers of these common prime factors are always higher in the numerator in your problem. Consequently, the fraction will always be an integer.