Combinatorial aspects of continued fractions. (English) Zbl 0445.05014

Author’s summary: We show that the universal continued fraction of the Stieltjes-Jacobi type is equivalent to the characteristic series of labelled paths in the plane. The equivalence holds in the set of series in non-commutative indeterminates. Using it, we derive direct combinatorial proofs of continued fraction expansions for series involving known combinatorial quantities: the Catalan numbers, the Bell and Stirling numbers, the tangent and secant numbers, the Euler and Eulerian numbers \(\dots\). We also show combinatorial interpretations for the coefficients of the elliptic functions, the coefficients of inverses of the Tchebycheff, Charlier, Hermite, Laguerre and Meixner polynomials. Other applications include cycles of binomial coefficients and inversion formulae. Most of the proofs follow from direct geometrical correspondences between objects.
Reviewer: R. C. Read


05A15 Exact enumeration problems, generating functions
05A10 Factorials, binomial coefficients, combinatorial functions
30B70 Continued fractions; complex-analytic aspects
11A55 Continued fractions
11B65 Binomial coefficients; factorials; \(q\)-identities
11B68 Bernoulli and Euler numbers and polynomials
11B73 Bell and Stirling numbers
Full Text: DOI


[1] de Bruijn, N.; Knuth, D.; Rice, S. O., The average height of planted plane trees, (Read, R. C., Graph Theory and Computing (1972), Academic Press: Academic Press New-York), 15-22 · Zbl 0247.05106
[2] Carlitz, L., A binomial identity arising from a sorting problem, SIAM Rev., 6, 20-30 (1964) · Zbl 0128.01601
[3] Carlitz, L., \(q\)-analog of the Lagrange expansion, (Eulerian Series and Applications (1974), Pennsylvania State University)
[4] Chihara, T. S., An Introduction to Orthogonal Polynomials (1978), Gordon and Breach: Gordon and Breach New-York · Zbl 0389.33008
[5] Comtet, L., Analyse Combinatoire, Vol. 2 (1970), P.U.F: P.U.F Paris · Zbl 0221.05001
[6] Cori, R., Un code pour les graphes planaires et ses applications, Astérisque, 27 (1975) · Zbl 0313.05115
[7] Dumont, D., Une nouvelle interprétation combinatoire des nombres tangents, 5-th Hungarian Conference on Combinatoircs, Keszthely (1976)
[8] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New-York · Zbl 0317.94045
[9] Flajolet, P., Analyse d’algorithmes de manipulation de fichiers, Rapport IRIA (1978), Rocquencourt
[10] P. Flajolet, J. Françon and J. Vuillemin, Analysis of data structures under sequences of operations (in preparation).; P. Flajolet, J. Françon and J. Vuillemin, Analysis of data structures under sequences of operations (in preparation).
[11] Foata, D.; Schützenberger, M. P., Théorie Géométrique des polynômes Euleriens, (Lecture Notes in Math., Vol. 138 (1970), Springer Verlag: Springer Verlag Berlin) · Zbl 0214.26202
[12] Françon, J., Histoires de Fichiers, RAIRO Inf. Th., 12, 49-62 (1978) · Zbl 0377.68034
[13] Françon, J.; Viennot, G., Permutations selon les pics, creux, doubles montées, doubles descentes, nombres d’Euler et nombres de Genocchi, Discrete Math., 28, 21-35 (1979) · Zbl 0409.05003
[14] Jackson, D. M., Some results on “Product-weighted lead codes”, J. Combinatorial Theory (Ser. A), 25, 181-187 (1978) · Zbl 0425.05007
[15] Knuth, D., The Art of Computer Programming: Fundamental Algorithm, Vol. 1 (1968), Addison Wesley: Addison Wesley Reading, MA · Zbl 0191.17903
[16] Kreweras, G., Sur une classe de problèmes de dénombrement liés au treillis de partition des entiers, Cahiers du B.U.R.O., 6 (1965), Paris
[17] Kreweras, G., Sur les éventails de segments, Cahiers du B.U.R.O., 15, 1-41 (1970), Paris
[18] Meixner, J., Orthogonale Polynomsysteme mit einem besonderen Gestalt der erzeugenden Funktion, J. Lond. Math. Soc., 9, 6-13 (1934) · Zbl 0008.16205
[19] Perron, O., Die Lehre von den Kettenbrüchen, Vol. 2 (1954), Teubner: Teubner Stuttgart
[20] Raney, G., Functional composition patterns and power series reversion, Trans. Am. Math. Soc., 94, 441-451 (1960) · Zbl 0131.01402
[21] Riordan, J., An Introduction to Combinatorial Analysis (1958), Wiley: Wiley New-York · Zbl 0078.00805
[22] Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New-York · Zbl 0194.00502
[23] Rogers, L. J., On the representation of certain asymptotic series as continued fractions, Proc. Lond. Math. Soc., 4, 2, 72-89 (1907)
[24] Rosen, J., The number of product-weighted lead codes for ballots and its relation to the Ursell function of the linear Ising model, J. Combinatorial Theory (Ser. A), 20, 377-384 (1976) · Zbl 0339.05009
[25] Schützenberger, M. P., On context-free languages and pushdown automata, Inf. and Control, 6, 246-264 (1963) · Zbl 0123.12502
[26] Stieltjes, T. J., Sur la réduction en fraction continue d’une série procédant suivant les puissances descendantes d’une variable, Ann. Fac. Sc. Toulouse, 3, 1-17 (1889)
[27] Strehl, V., Enumeration of alternating permutations according to peak sets, J. Combinatorial Theory (Ser. A), 24, 238-240 (1978) · Zbl 0373.05005
[28] Touchard, J., Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4, 2-25 (1952) · Zbl 0047.01801
[29] G. Viennot, Une interprétation combinatoire des dévelopements en série entière des fonctions elliptiques de Jacobi (to appear).; G. Viennot, Une interprétation combinatoire des dévelopements en série entière des fonctions elliptiques de Jacobi (to appear). · Zbl 0444.33002
[30] Wall, H. S., Analytic Theory of Continued Fractions (1967), Chelsea: Chelsea New-York · Zbl 0035.03601
[31] Whittaker, E. T.; Watson, G. N., A Course of Modern Analysis (1927), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0108.26903
[32] Read, R. C., The chord intersection problem, Annals of New-York Ac. of Sc., 319, 444-454 (1979) · Zbl 0479.05005
[33] Flajolet, P., Analyse d’algorithmes de manipulation d’arbres et de fichiers, Thèse, Fac. Sc. Orsay (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.