7
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – joro
    Sep 10, 2012 at 11:30

4 Answers 4

16
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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

$\endgroup$
2
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)

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