Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? Thank you.

share|cite|improve this question
Prove that the factorial ratio satisfies a two-term recurrence relation with integer coefficients and integer initial value. – user02138 Oct 17 '12 at 3:26
I wonder if there isn't some way to make this into a product of binomial coefficients. – MJD Oct 17 '12 at 5:00
This was a 1972 IMO problem – Jeremy Oct 17 '12 at 5:40
Is there a way to interpret this expression as counting something? – pad Dec 17 '14 at 19:16
up vote 5 down vote accepted

Denote $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ by $S(n,m)$. It satisfies relation $S(n+1,m)+S(n,m+1)=4S(n,m)$ (cf. Pascal's triangle) — or, equivalently, $S(n+1,m)=4S(n,m)-S(n,m+1)$. Since $S(0,m)=\binom{2m}m$ is an integer, this relation implies that all $S(n,m)$ are integers.

Ref.: I. Gessel. Super Ballot Numbers (via MO)

share|cite|improve this answer

Consider a prime $p$. The highest power of $p$ dividing the numerator is $$\alpha_{Nr} = \left(\left \lfloor \dfrac{2m}{p}\right \rfloor + \left \lfloor \dfrac{2m}{p^2}\right \rfloor + \left \lfloor \dfrac{2m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{2n}{p}\right \rfloor + \left \lfloor \dfrac{2n}{p^2}\right \rfloor + \left \lfloor \dfrac{2n}{p^3}\right \rfloor + \cdots \right)$$

The highest power $p$ dividing the denominator is $$\alpha_{Dr} = \left(\left \lfloor \dfrac{m}{p}\right \rfloor + \left \lfloor \dfrac{m}{p^2}\right \rfloor + \left \lfloor \dfrac{m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{n}{p}\right \rfloor + \left \lfloor \dfrac{n}{p^2}\right \rfloor + \left \lfloor \dfrac{n}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{m+n}{p}\right \rfloor + \left \lfloor \dfrac{m+n}{p^2}\right \rfloor + \left \lfloor \dfrac{m+n}{p^3}\right \rfloor + \cdots \right)$$

You may want to look at this post that discusses the highest power of a prime dividing $N!$.

The goal now is to show that $\alpha_{Nr} > \alpha_{Dr}$. If we prove that $$\lfloor 2x \rfloor + \lfloor 2y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$ we are then done. Can you now prove this one?

We have $x = \lfloor x \rfloor + \{x \}$ and $y = \lfloor y \rfloor + \{y \}$.

We will consider 4 cases.

Case $1$: $\{x\} <1/2$, $\{y\} <1/2$. Then $\lfloor 2x \rfloor = 2 \lfloor x \rfloor$ and $\lfloor 2y \rfloor = 2 \lfloor y \rfloor$ and $\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor$. Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $2$: $\{x\} <1/2$, $\{y\} >1/2$ or $\{x\} >1/2$, $\{y\} <1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 1$$ Further, $$\lfloor x+y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $3$: $\{x\} >1/2$, $\{y\} >1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 2$$ Further, $$\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor > \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.