# When does doubling the size of a set multiply the number of subsets by an integer?

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.

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.

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. 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$. 