8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Have you looked at the book: Analytic Combinatorics by Flajolet? $\endgroup$
    – Suvrit
    Commented Mar 4, 2016 at 17:19
  • $\begingroup$ Have a look at the recent cambridge.org/us/academic/subjects/mathematics/number-theory/… $\endgroup$
    – Will Jagy
    Commented Mar 4, 2016 at 19:02
  • $\begingroup$ @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. $\endgroup$
    – user40023
    Commented Mar 4, 2016 at 19:22
  • $\begingroup$ 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). $\endgroup$
    – Suvrit
    Commented Mar 4, 2016 at 19:32

3 Answers 3

Reset to default
5
$\begingroup$

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.
Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.