Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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

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

V space

Voineasa.

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

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.