30
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

34
$\begingroup$

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

$\endgroup$
21
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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