# Problems in Factorials

Here's a simple fact:

Product of n consecutive integers is divisible by n!.

The simplest of the proofs is combinatorial: after all, the binomial coefficient {n+m \choose m} = \frac{(n+m)!}{n!m!} is an integer, so that the product (m+1)(m+2)\cdot...\cdot(m+n) is divisible by n!.

As a particular case, (2n)! is divisible by (n!)^{2}. But, to complicate things, a stronger assertion is true:

\frac{(2n)!}{n!} is divisible by (n+1)!.

I met this problem in a Russian collection of olympiad problems as an assertion that \frac{(2n)!}{(n!)^{2}} is divisible by n+1.

For a proof, consider another binomial coefficient (and, hence, an integer) {{2n} \choose {n+1}} = \frac{(2n)!}{(n-1)!(n+1)!} .

Let A = \frac{(2n)!}{(n!)^{2}} and B = \frac{(2n)!}{(n-1)!(n+1)!}. Then

An = \frac{(2n)!}{(n-1)!n!} = B(n+1).

This implies that n+1 divides An, but, since n+1 and n are mutually prime, it follows by Euclid's Lemma (Elements, VII.30) that n+1 divides A.

Incidently, quantity {\frac{1}{n+1}}{2n \choose {n}} is well known in combinatorics as the Catalan number. Catalan numbers arise in a multitude of counting scenarios.

\frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{n!(n+1)!} = \frac{1}{2n+1}{2n+1 \choose n}.

E. Catalan proved more general results [Dickson, p. 265-267] . For example,

\frac{(m+n-1)!}{m!n!}

is integer, provided m and n are mutually prime. This is a direct generalization of the above. Also

\frac{(2m)!(2n)!}{m!n!(m+n)!} = {{2m \choose m}{2n \choose n}} \div {n+m \choose n}

is integer for integer n and m.

Here is another one [Nagell, p. 124] :

(nm)! is divisible by n!(m!)^{n}.

References

1. L. E. Dickson, History of the Theory of Numbers, v 1, Dover, 2005
2. T. Nagell, Introduction to Number Theory, Chelsea, 1981