I am interested in a weighted version of the Catalan numbers. The generating function for this case, $$ f(x, y) = \sum_s \sum_n f_{s n} x^s y^n $$ (where the $y^n$ term is the weight), obeys the relation $$ f(x, y) = 1 + x y f(x, y) f(xy, y) $$

Main question:

Is there any hope of solving for $f(x, y)$ in closed form? Alternately, I'd be happy to get a closed form for the coefficients of the series expansion in $x$ of $f(x, y)$ at $x=0$ and a particular value of $y$, where $0 < y < 1$. An exact expression is not required; a good approximation will serve just as well.


-I haven't encountered any methods for solving such a problem before, so I don't know if there is a name for such problems. I apologize if the title and keywords are uninformative.

-Obviously when $y=1$, this reduces to the ordinary Catalan numbers.

-I believe that it may be possible to turn this into a coupled set of PDEs by defining $g(x, y) = f(xy, y)$. However, this seems to make the problem more complicated rather than less so.

-Since $f(xy, y)$ is known in terms of $f(x, y)$, we may be able to learn about the series at $x=0$ by examining the sequence $f(x y^m, y)$ as $m \to \infty$. However, I haven't been able to make this idea work in any concrete way yet.

Any ideas are appreciated. Thanks!

Edit: As Mark noted, this comes from trying to solve a recurrence relation of the form $$ f_{sn} = \sum_{s_1 + s_2 + 1 = s} \sum_{n_1 + n_2 + s_1 + 1 = n} f_{s_1 n_1} f_{s_2 n_2} $$ This arises when considering the first-return times in a one-dimensional discrete random walk where the probability of moving to the right decreases exponentially with position.

  • $\begingroup$ I can use the relation to get a recurrence relation among the $f_{sn}$, but I assume that is what you started from and you are looking to the generating function method to help get your series expansion. So that recurrence relation is of no use to you because you already have it, right? $\endgroup$ Jun 28, 2016 at 20:05
  • $\begingroup$ Observation: You can get pretty far for fixed $y$ near $\frac12$ by doing a continued fraction expansion by iterating the equation. $\endgroup$ Jun 28, 2016 at 23:01
  • $\begingroup$ @MarkFischler Thanks. Yes, I started with the recurrence relation. The recurrence relation is slightly asymmetric, which is what leads to the asymmetry in the equation given above. I'll add it to the question. $\endgroup$
    – sasquires
    Jun 29, 2016 at 15:45
  • $\begingroup$ @MarkFischler I considered using a continued fraction to look at $f(xy^m, y)$. However, it's not clear how this relates to the series for $f(x, y)$. As $m \to \infty$, then we should just get an expression for $f(0, y)$ rather than an expression for the series. Did you have something else in mind? Also, why does it help to have $y \approx 1/2$? $\endgroup$
    – sasquires
    Jun 29, 2016 at 15:47
  • $\begingroup$ The continued fraction expansion you get has $x$ in each of the terms. BTW, the easiest continued fraction expansion has 2 as the constant and a simple expression in the numerators of each of the fractions, rather than the usual form of expressions as the constants and 1 as all the numerators. I thought it would be easy to go between the two forms, but I don't see how. $\endgroup$ Jul 1, 2016 at 19:22

2 Answers 2


It seems experimentally that \begin{align*} f_{ss} &= 1 & \text{ for } s \geq 0 \\ f_{s,s+1} &= s-1 & \text{ for } s \geq 1 \\ f_{s,s+2} &= \left(\begin{array}{c}s-1\\2\end{array}\right) & \text{ for } s \geq 1 \\ f_{s,s+3} &= \left(\begin{array}{c}s-2\\1\end{array}\right) + \left(\begin{array}{c}s-2\\2\end{array}\right) + \left(\begin{array}{c}s-2\\3\end{array}\right) & \text{ for } s \geq 2. \end{align*} There does not seem to be a similarly tidy expression for $f_{s,s+4}$.

  • $\begingroup$ Thanks! I am interested in summing over all $n$, so I can't use this directly right now, but it may be a hint in the right direction. $\endgroup$
    – sasquires
    Jun 29, 2016 at 16:18
  • $\begingroup$ Although it wasn't a solution, you made a most serious attempt at an answer, so I awarded the bounty to you so that it wouldn't go to waste. $\endgroup$
    – sasquires
    Jul 14, 2016 at 21:27

I recently started thinking about this problem again. Here is the best I have. It is possible to turn the constraint on $f$ into a continued fraction. (This may be what Mark was thinking in the comments above.) Specifically, $$ f(x, y) = \frac{1}{1 - x y f(xy, y)} $$ so $$ f(x, y) = \frac{1}{1 - \frac{x y}{1 - \frac{x y^2}{1 - \dots}}} $$

There is an explicit closed-form expression for the series arising from such a continued fraction, provided by P. Flajolet in this 1980 paper. This expression is not as simple as I would have liked, but it makes the problem feasible again.


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.