# “Ballot numbers” sum up to Catalan numbers

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

-
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"? – john_leo Jun 21 '12 at 17:31
@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$. – 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)$.

Voineasa.

-
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/… – gnometorule Feb 13 '13 at 20:25
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. – john_leo Feb 14 '13 at 10:48
Forget the "shortest path" part, sorry about that one. I was confused because of the different ballot number definitions. – john_leo Feb 14 '13 at 10:56