MathOverflow is a question and answer site for professional mathematicians. 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

Recently, I got interested in the study of the combinatorial aspects of continued fractions. Precisely, I read of the following lemma of Flajolet (see here):

Lemma. It holds $$\sum_{\omega} \nu(\omega) \, z^{|\omega|} = \frac1{1 - c_0 z - \displaystyle\frac{a_0b_0z^2}{1 - c_1 z - \displaystyle\frac{a_1 b_1 z^2}{1 - c_2 z - \ldots}}} ,$$ where $\omega$ runs over all the Motzkin paths, $|\omega|$ is the length of the Motzkin path $\omega$, and $\nu(\omega)$ is its weight, assigning the weights $a_i$, $b_i$, and $c_i$ to up, down, and horizontal steps, respectively (see the linked PDF for more details).

I would like to know more about this kind of connections between combinatorics and continued fractions and I am looking for a book about this subject, or at least with a detailed chapter about.

Until know I just found some articles, all pointing to the 1980 article of Flajolet (1). I also see that the book (2) has a chapter on "Combinatorial interpretations of continued fractions", but it regards tilings and continued fractions with integers numerators and denominators, so it is about other things. The lecture notes of Viennot (3) might be good, but I cannot read French and they are only 3 years after Flajolet paper, it would be better something more updated.

Thank you in advance for your help.

(1) P. Flajolet, Combinatorial aspects of continued fractions, Discrete Mathematics 32 (1980) 125--161.

(2) A. T. Benjamin, J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

(3) Une theorie combinatoire des polynomes orthogonaux generaux

share|cite|improve this question
Have you looked at the book: Analytic Combinatorics by Flajolet? – Suvrit Mar 4 at 17:19
Have a look at the recent… – Will Jagy Mar 4 at 19:02
@Suvrit I checked P. Flajolet, Analytic Combinatorics and indeed the lemma in my question is in section "V. 4. Nested sequences, lattice paths, and continued fractions" with a quite detailed description, thanks! I would accept it as an answer, but first I wait to see if somebody has other references. – Fry Mar 4 at 19:22
Yep, that's the section I had in mind (I briefly glanced through the TOC of that book, but was not sure if you had already seen it). – Suvrit Mar 4 at 19:32
up vote 5 down vote accepted

One book that I know which covers this topic is (available online): Analytic Combinatorics, P. Flajolet and R. Sedgewick. In particular, (as the OP now also notes in a comment), the relevant section is V.4.

The following slides of Flajolet are also relevant.


  1. The OP may also find this paper on restricted permutations and continued fractions of interest.
  2. Another interesting reference (not on the original topic, but I thought it worthwhile to mention here) is: Analytic Combinatorics in Several Variables, by R. Pemantle and M. Wilson.
share|cite|improve this answer

Hint: No book recommendation, but in case you are not aware of it you might appreciate the nice survey Combinatorial aspects of continued fractions and applications by Xavier G. Viennot in honor of P. Flajolet.

share|cite|improve this answer

See Chapter 5 of the book Combinatorial Enumeration by Ian P. Goulden and David Jackson, Wiley, 1983, reprinted by Dover in 2004.

share|cite|improve this answer

Your Answer


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.