Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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

4 Answers 4

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|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:

http://arxiv.org/abs/math/9811086

share|improve this answer
1  
See also math.harvard.edu/~elkies/Misc/catalan.pdf and math.harvard.edu/~elkies/Misc/catalan2.pdf 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: http://www.math.miami.edu/~armstrong/RCCinDC.pdf

As this paper explains, they are a further generalization of Fuss-Catalan numbers: http://arxiv.org/abs/1305.7286

share|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|improve this answer

Your Answer

 
discard

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.