Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We have the following recurrence relation for $a_{n,m}$


with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ are the Catalan numbers and $a_{0,m}=0$ for $m>0$. After defining the generating function

$\phi(x,y)=\sum_{n,m=0}^\infty x^n y^m a_{n,m}$

the relation becomes an easy quadratic equation for $\phi(x,y)$ which basically solves the problem. This equation however involves $A(y)=\sum_{m=0}^\infty y^m a_{1,m}$ as a parameter, which is not given by the boundary condition. Anybody any ideas on how this $A(y)$ can be determined from the recursion rules without knowing the solution for $a_{n,m}$?

share|cite|improve this question
This isn't really a recurrence relation for $a_{n,m}$, since $a_{n,m}$ occurs on both sides and cancels out (since $a_{0,0}=1$). Perhaps you should regard it as a recurrence relation for $a_{n+1,m-1}$? – joriki Sep 25 '12 at 8:07
I'm wondering: If we set $a_{n,-1}=0$, the recurrence for $a_{n,0}$ looks similar to the one for the Catalan numbers; they'd coincide if we had $n+1$ on the left and the sum on the right ran up to $n$. That makes me wonder whether you've got a typo in there somewhere, since the relation would make much more sense if the left-hand side didn't occur in the sum on the right and if the Catalan numbers as initial values came out as a special case of the recurrence. – joriki Sep 25 '12 at 9:12
Yes, there was a typo $\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-i,m-j} ---> \sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$ sorry about that. – Juraj Sep 25 '12 at 16:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.