Summing certain numbers and comparing the results with OEIS, I found that $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $

where $C_n$ denotes the $n^{\textrm{th}}$ Catalan Number. How can I prove this equation? And is there any combinatorial interpretation?

Some background information: The number $\frac{k}{n} \binom{2n-k-1}{n-1}$ denotes the number of unranked trees of size $n$ with a root degree $k$ (these numbers are known as ballot numbers, see e.g. the book Analytic Combinatorics from Flajolet and Sedgewick, page 68). So one must have $\sum_{k=1}^n \frac{k}{n} \binom{2n-k-1}{n-1} = C_{n}$, since there are $C_n$ many trees of size $n$.


Notice that: $$ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} \stackrel{k \to n+1-k}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{n-1} \stackrel{\binom{a}{b} = \binom{a}{a-b}}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{k-1} = \sum_{k=0}^{n} \frac{(n-k)^2}{n} \binom{n+k-1}{k} $$ This this nothing but a convolution of two sequences $a_{k} = \frac{k^2}{n}$ and $b_{k} = \binom{n+k-1}{k}$. Therefore the generating function for the sum $c_n = \sum_{k=0}^{n} a_{n-k} b_k$ is the product of generating functions of $a_k$ and $b_k$: $$ \sum_{k=0}^\infty x^k a_k = \frac{1}{n} \sum_{k=0}^\infty x^k k^2 = \frac{1}{n} \left( x\frac{\mathrm{d}}{\mathrm{d} x}\right)^2 \sum_{k=0}^\infty x^k = \frac{1}{n} \frac{x(1+x)}{(1-x)^3} $$ $$ \sum_{k=0}^\infty \binom{n+k-1}{k} x^k = \frac{1}{(1-x)^n} $$ Thus: $$ c_n = [x]^n \left( \frac{1}{n} \frac{x(1+x)}{(1-x)^3} \frac{1}{(1-x)^n} \right) = [x]^n \left( \frac{1}{n} \frac{x}{(1-x)^{n+3}} + \frac{1}{n} \frac{x^2}{(1-x)^{n+3}} \right) = \frac{1}{n} \left(\binom{2n+1}{n-1} + \binom{2n}{n-2} \right) $$ Now, using $$ \binom{2n}{n-2} = \binom{2n+1}{n-1} - \frac{2n}{n-1} \binom{2n-1}{n-2} $$ which is easily proven using recurrence relation for factorials comprising binomial coefficients, we get $$ c_n = \frac{2}{n} \binom{2n+1}{n-1} - \frac{2}{n-1} \binom{2n-1}{n-2} = C_{n+1} - C_{n} $$

  • $\begingroup$ Thanks. Is there an easy way to see that $[x]^n \frac{x}{(1-x)^{n+3}} = \binom{2n+1}{n-1}$, or is it a lot of "tayloring"? $\endgroup$
    – john_leo
    Jun 21 '12 at 17:31
  • $\begingroup$ @john_leo You start with $b_k = [x]^k \frac{1}{(1-x)^n} = \binom{n+k-1}{k}$, replace $n \to n+3$, and $k$ with $n-1$ and $n-2$. $\endgroup$
    – Sasha
    Jun 21 '12 at 17:39

Consider the space of lattice points $(p,q)$ where $0 \leq p \leq q, q = 0, 1, \dots$; the number of (shortest) paths in this space from $(p,q)$ to $(0,0)$ is the ballot number $$N(p,q) = \frac{q-p+1}{q+1} \cdot \binom{p+q}{p}; \quad N(0,0) =_D 1.$$ Using this notation we have $ N(n-k,n-1) = \frac{k}{n} \binom{2n-k-1}{n-1} $. The problem asks to show $$\sum_{k=1}^n k N(n-k, n-1) = C_{n+1} - C_{n}.$$

Note that $ C_{n} $ is the nth Catalan number and that $ C_{n} = N(n,n) $, so $ C_{n+1} - C_{n} $ is the number of paths from point $(n-1, n+1)$ to $(0,0)$ (all paths from $(n+1, n+1)$ to $(0,0)$ which don't use point $(n,n)$ must use point $(n-1, n+1)$).

Any path from point $(n-1, n+1)$ to point $(0,0)$ must use one and only one of the arcs $a(k)$ which start from point $(k, n)$ and stop in point $(k, n-1)$, where $0 \leq k \leq n-1$. But the number of such paths is $(n-k)N(k,n-1)$ because the number of paths from $(n-1, n+1)$ to point $(k, n)$ is $(n-k)$, and the number of paths from point $(k,n)$ which use arc $a(k)$ is $N(k,n-1)$, so the total number of paths from point $(n-1, n+1)$ to $(0,0)$ is $\sum_{k=0}^{n-1} (n-k) N(k,n-1)$.

V space


  • $\begingroup$ Welcome to MSE! The site use MathJax to pretty up the math font, which is essentially Tex between dollar signs. For future submissions, you might find this useful: meta.math.stackexchange.com/questions/5020/… $\endgroup$ Feb 13 '13 at 20:25
  • $\begingroup$ Thanks for your answer. There are a few things I don't understand: First of all, what exactly is a "shortest path" in a lattice? Then, does $C(p+q,p)$ denote the binomial coefficient (it's confusing to have $C(n)$ for the Catalan number and $C(n,p)$ for the binomial coefficient)? And where did you get your ballot number formula from? It's not the same as the one I have (just check that for n=k resp. p=q the values are different). Searching the net now I found that there are many different ballot number formulas out there. $\endgroup$
    – john_leo
    Feb 14 '13 at 10:48
  • $\begingroup$ Forget the "shortest path" part, sorry about that one. I was confused because of the different ballot number definitions. $\endgroup$
    – john_leo
    Feb 14 '13 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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