# Combinatorial aspects of continued fractions

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

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.

(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 http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html

-
Have you looked at the book: Analytic Combinatorics by Flajolet? – Suvrit Mar 4 at 17:19
Have a look at the recent cambridge.org/us/academic/subjects/mathematics/number-theory/… – 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

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.

Remarks

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

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.

-

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

-