MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

It is well-known that the $n$th Catalan number is equal to $(n+1)^{-1}\binom{2n}{n}$. A long time ago I had wondered what happens if you look at the sequence generated by $(n+k)^{-1}\binom{pn}{n}$ - for which $p,k$ is it integral?

I found no other integral-producing values except for $(p,k)=(2,1)$ but then I'm probably missing something. (Also, MATLAB, which is my main tool, quickly runs out of precision on this kind of computation).

So - is this known? Trivial, perhaps?

share|cite|improve this question
With sage can't find other (p,k) even with the relaxation the first few terms to be nonintegral. (12,1) and (18,1) are very rarely nonintegral though. – joro Sep 10 '12 at 11:30
up vote 15 down vote accepted

Yes, $(p,k)=(2,1)$ is the only case when the sequence is integral.

We always need $p\geq 2$. First let's pick a prime $q$ which is $\geq k$ and which divides one of the numbers in $\lbrace pk-1,pk-2,\dots,pk-k\rbrace$. This always exists for $k\geq 2$ by a famous result of Sylvester.

Now taking $n=q-k$, it is easy to check that $n+k$ does not divide $pn(pn-1)\cdots((p-1)n+1)$ and so $\frac{1}{n+k}\binom{pn}{n}$ is not an integer.

share|cite|improve this answer

Maybe you are looking for the Fuss-Catalan numbers?

These are given by $\frac{1}{(s-1)n+1}\binom{sn}{n}$.

A starting point for the combinatorial significance of these numbers is:

share|cite|improve this answer
See also and for elementary proofs of the formula for the relevant generating function. – Noam D. Elkies Sep 10 '12 at 13:41
I accepted the other answer because it answered directly the question which I had for years - but this one is also very good! – Felix Goldberg Sep 10 '12 at 16:41

You might also be interested in the rational Catalan numbers, defined for $(a,b)=1$ as $\mathrm{Cat}(a,b) := \frac{1}{a+b}\binom{a+b}{a}$.

See these slides by Drew Armstrong for their significance:

As this paper explains, they are a further generalization of Fuss-Catalan numbers:

share|cite|improve this answer

One more related oject is the Catalan's triangle with integer entries $$B(n,r)=\frac rn{2n\choose n-r}$$ (see also the free book Catalan Numbers With Applications - T Koshy (Oxford, 2009)

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.