For natural numbers $m, r$, consider the ratio of the number of subsets of size $m$ taken from a set of size $2(m+r)$ to the number of subsets of the same size taken from a set of size $m+r$:

$$R(m,r)=\frac{\binom{2(m+r)}{m}}{\binom{m+r}{m}}$$

For $r=0$ we have the central binomial coefficients, which of course are all integers:

$$R(m,0)=\binom{2m}{m}$$

For $r=1$ we have the Catalan numbers, which again are integers:

$$R(m,1)=\frac{\binom{2(m+1)}{m}}{m+1}=\frac{(2(m+1))!}{m!(m+2)!(m+1)}=\frac{(2(m+1))!}{(m+2)!(m+1)!}=C_{m+1}$$

However, for any fixed $r\ge 2$, while $R(m,r)$ seems to be mostly integral, it is not exclusively so. For example, with $m$ ranging from 0 to 20000, the number of times $R(m,r)$ is an integer for $r=2,3,4,5$ are 19583, 19485, 18566, and 18312 respectively.

I am seeking general criteria for $R(m,r)$ to be an integer.

Edited to add:

We can write:

$$R(m,r) = \prod_{k=1}^m{\frac{m+2r+k}{r+k}}$$

So the denominator is the product of $m$ consecutive numbers $r+1, \ldots, m+r$, while the numerator is the product of $m$ consecutive numbers $m+2r+1,\ldots,2m+2r$. So there is a gap of $r$ between the last of the numbers in the denominator and the first of the numbers in the numerator.

up vote 31 down vote accepted

Put $n=m+r$, and then we can write $R(m,r)$ more conveniently as $$ R(m,r) = \frac{(2n)!}{m! (n+r)!} \frac{m! r!}{n!} = \frac{\binom{2n}{n} }{\binom{n+r}{r}}. $$ So the question essentially becomes one about which numbers $n+k$ for $k=1$, $\ldots$, $r$ divide the middle binomial coefficient $\binom{2n}{n}$. Obviously when $k=1$, $n+1$ always divides the middle binomial coefficient, but what about other values of $k$? This is treated in a lovely Monthly article of Pomerance.

Pomerance shows that for any $k \ge 2$ there are infinitely many integers with $n+k$ not dividing $\binom{2n}{n}$, but the set of integers $n$ for which $n+k$ does divide $\binom{2n}{n}$ has density $1$. So for any fixed $r$, for a density $1$ set of values of $n$ one has that $(n+1)$, $\ldots$, $(n+r)$ all divide $\binom{2n}{n}$, which means that their lcm must divide $\binom{2n}{n}$. But one can check without too much difficulty that the lcm of $n+1$, $\ldots$, $n+r$ is a multiple of $\binom{n+r}{r}$, and so for fixed $r$ one deduces that $R(m,r)$ is an integer for a set of values $m$ with density $1$. (Actually, Pomerance mentions explicitly in (5) of his paper that $(n+1)(n+2)\cdots (n+r)$ divides $\binom{2n}{n}$ for a set of full density.)

Finally let me show that $R(m,r)$ is not an integer infinitely often when $r \ge 2$ is fixed. Let $p$ be a prime with $r<p <2r$; such a prime exists by Bertrand's postulate. Now take $n=p^a - r$ for any natural number $a$. Then note that $p^a$ exactly divides $\binom{n+r}{r}$, and that the power of $p$ dividing $\binom{2n}{n}$ is $$ \sum_{j=1}^{a} \Big( \Big\lfloor \frac{2(p^a-r)}{p^j} \Big\rfloor - 2\Big\lfloor \frac{p^a-r}{p^j}\Big \rfloor \Big) =a-1, $$ since the term $j=1$ contributes $0$ and the other terms contribute $1$.

Just an illustration - for $m$ up to 6000, $r$ up to 120. Quite mysterious looking, I would say.

enter image description here

Version 2: in the coordinate system suggested by the answer of Lucia it looks somehow more regular, although, I believe, even more mysterious. Click if you want to enlarge.

This is now the plot of pairs $(n,r)$ with $\binom{n+r}n$ dividing $\binom{2n}n$.

enter image description here

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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