## PHILIPPE FLAJOLET's RESEARCH PAPERS

You're welcome to some recent (...and not so recent) work of Philippe.Flajolet@inria.fr in electronic form.
These are in postscript and pdf format, also compressed with GNU's gzip. These documents are for preview. They correspond to versions submitted (without copy editing, before refereeing, etc). Consequently, they only represent a rough approximation to the published versions to which you are encouraged to refer. See the publication list for a complete listing of my paper publications.

## 2010 Happy 2010!

• The Enumeration of Prudent Polygons by Area and its Unusual Asymptotics By Nick Beaton, Philippe Flajolet, and Tony Guttmann. In arXiv:1011.6195v1 [math.CO], November 29, 2010. 27 pages. Submitted to Journal of Combinatorial Theory, Series A.

Prudent walks are special self-avoiding walks that never take a step towards an already occupied site, and k-sided prudent walks (with k=1,2,3,4) are, in essence, only allowed to grow along k directions. Prudent polygons are prudent walks that return to a point adjacent to their starting point. Prudent walks and polygons have been previously enumerated by length and perimeter (Bousquet-Mélou, Schwerdtfeger; 2010). We consider the enumeration of prudent polygons by area. For the 3-sided variety, we find that the generating function is expressed in terms of a q-hypergeometric function, with an accumulation of poles towards the dominant singularity. This expression reveals an unusual asymptotic structure of the number of polygons of area~n, where the critical exponent is the transcendental number log2(3) and and the amplitude involves tiny oscillations. Based on numerical data, we also expect similar phenomena to occur for 4-sided polygons. The asymptotic methodology involves an original combination of Mellin transform techniques and singularity analysis, which is of potential interest in a number of other asymptotic enumeration problems.

• On Buffon Machines and Numbers [Extended abstract]. By Philippe Flajolet, Maryse Pelletier, and Michèle Soria. To appear in ACM-SIAM Sympoium on Discrete Algorithms (SODA), San Francisco, January 2011, 12 pages
(Much revised version of the earlier arXiv:0906.5560.) [slides in PDF: 6MB]

The well-know needle experiment of Buffon can be regarded as an analog (i.e., continuous) device that stochastically ``computes'' the number 2/π~0.63661, which is the experiment's probability of success. Generalizing the experiment and simplifying the computational framework, we consider probability distributions, which can be produced perfectly, from a discrete source of unbiased coin flips. We describe and analyse a few simple Buffon machines that generate geometric, Poisson, and logarithmic-series distributions. We provide human-accessible Buffon machines, which require a dozen coin flips or less, on average, and produce experiments whose probabilities of success are expressible in terms of numbers such as π, exp(-1), log2, √3, cos(1/4), ζ(5). Generally, we develop a collection of constructions based on simple probabilistic mechanisms that enable one to design Buffon experiments involving compositions of exponentials and logarithms, polylogarithms, direct and inverse trigonometric functions, algebraic and hypergeometric functions, as well as functions defined by integrals, such as the Gaussian error function.
• Combinatorial Models of Creation-Annihilation. By Pawel Blasiak and Philippe Flajolet. Preprint, October 2010. In arXiv.org>math>arXiv:1010.0354. 75 pages, 26 figures. Preview version. Comments welcome, especially before mid-November 2010, when the paper is going to be submitted..
Subjects: Combinatorics (math.CO); Mathematical Physics (math-ph); Quantum Physics (quant-ph). MSC classes: 05A15 (Primary), 81R15 (Secondary). Cite as: arXiv:1010.0354v1 [math.CO]

Quantum physics has revealed many interesting formal properties associated with the algebra of two operators, A and B, satisfying the partial commutation relation AB-BA=1. This study surveys the relationships between classical combinatorial structures and the reduction to normal form of operator polynomials in such an algebra. The connection is achieved through suitable graphs, or "diagrams", that are composed of elementary "gates". In this way, many normal form evaluations can be systematically obtained, thanks to models that involve set partitions, permutations, increasing trees, as well as weighted lattice paths. Extensions to q-analogues, multivariate frameworks, and urn models are also briefly discussed.
• The distribution of height and diameter in random non-plane binary trees. By Nicolas Broutin and Philippe Flajolet. arXiv.org>math>arXiv:1009.1515, September 2010, 33 pages. Submitted to Random Structures & Algorithms.

This study is dedicated to precise distributional analyses of the height of non-plane unlabelled binary trees ("Otter trees"), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size \$n\$ is proved to admit a limiting theta distribution, both in a central and local sense, as well as obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height.

This version of September 2010 subsumes the earlier extended abstract:

• The unusual asymptotics of 3-sided prudent polygons. Nicholas Beaton, Philippe Flajolet, Anthony Guttmann. 12 pages. In J. Phys. A: Math. Theor., vol 43:34 (2010) 342001, pp.~1--10. Version of June 24, 2010.

We have studied the area generating function of prudent polygons on the square lattice. Exact solutions are obtained for the generating function of two-sided and three-sided prudent polygons, and a functional equation is found for four-sided prudent polygons. This is used to generate series coefficients in polynomial time, and these are analysed to determine the asymptotics numerically. A careful asymptotic analysis of the three-sided polygons produces a most surprising result. A transcendental critical exponent is found - and the leading amplitude is not quite a constant, but is a constant plus a small oscillatory component with an amplitude approximately $10-8$ times that of the leading amplitude. This effect cannot be seen by any standard numerical analysis, but it may be present in other models. If so, it changes our whole view of the asymptotic behaviour of lattice models.
• Digital Trees and Memoryless Sources: from Arithmetics to Analysis. Philippe Flajolet, Mathieu Roux, and Brigitte Vallée. To appear in AofA'10, Wien, June 2010. Proceedings to be published in DMTCS, 2010, 27 pages.

Digital trees, also known as "tries", are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the memoryless source, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous Dirichlet series. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific arithmetic properties, especially irrationality measures, of the sources under consideration.

• Pseudo-factorials, elliptic functions, and continued fractions. Roland Bacher and Philippe Flajolet. In The Ramanujan Journal, 21 (2010), pp. 71--97. (Also available as arXiv:0901.1379.)

This study presents miscellaneous properties of pseudo-factorials, which are numbers whose recurrence relation is a twisted form of that of usual factorials. These numbers are associated with special elliptic functions, most notably, a Dixonian and a Weierstrass function, which parametrize the Fermat cubic curve and are relative to a hexagonal lattice. A continued fraction expansion of the ordinary generating function of pseudo-factorials, first discovered empirically, is established here. This article also provides a characterization of the associated orthogonal polynomials, which appear to form a new family of ''elliptic polynomials'', as well as various other properties of pseudo-factorials, including a hexagonal lattice sum expression and elementary congruences.

• Lindelöf Representations and (Non-)Holonomic Sequences. Philippe Flajolet, Stefan Gerhold and Bruno Salvy. In Electronic Journal of Combinatorics, vol 17(1):R3, pp. 1--28. Published January 2010. (Also available as arXiv:0906.1957, June 2009.)

Various sequences that possess explicit analytic expressions can be analysed asymptotically through integral representations due to Lindelöf, which belong to an attractive but somewhat neglected chapter of complex analysis. One of the outcomes of such analyses concerns the non-existence of linear recurrences with polynomial coefficients annihilating these sequences, and, accordingly, the non-existence of linear differential equations with polynomial coefficients annihilating their generating functions. In particular, the corresponding generating functions are transcendental. Asymptotic estimates of certain finite difference sequences come out as a byproduct of the Lindelöf approach.

## 2009

• The Number of Symbol Comparisons in QuickSort and QuickSelect. Brigitte Vallée, Julien Clément, Jim Fill, and Philippe Flajolet. In Proceedings of ICALP 2009 (36th International Colloquium on Automata, Languages and Programming). In Lecture Notes in Computer Science, S Alberts et al. Ed, vol 5555, pp 750--763.

We revisit the classical QuickSort and QuickSelect algorithms, under a complexity model that fully takes into account the elementary comparisons between symbols composing the records to be processed. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. We establish that, under our conditions, the average-case complexity of QuickSort is O(n log^2 n) [rather than O(n log n), classically], whereas that of QuickSelect remains O(n). Explicit expressions for the implied constants are provided by our combinatorial-analytic methods.

• Isomorphism and Symmetries in Random Phylogenetic Trees. Miklós Bóna and Philippe Flajolet. In Journal of Applied Probability, vol 46 (2009), pp. 1005--1019. Available as arXiv:0901.0696v2 (January 2009), 14 pages.

The probability that two randomly selected phylogenetic trees of the same size are isomorphic is found to be asymptotic to a decreasing exponential modulated by a polynomial factor. The number of symmetrical nodes in a random phylogenetic tree of large size obeys a limiting Gaussian distribution, in the sense of both central and local limits. The probability that two random phylogenetic trees have the same number of symmetries asymptotically obeys an inverse square-root law. Precise estimates for these problems are obtained by methods of analytic combinatorics, involving bivariate generating functions, singularity analysis, and quasi-powers approximations.

•   ANALYTIC COMBINATORICS . 824 pages. Edition of June 26, 2009 (stable). Complete free PDF file with all Chapters/Appendices/References in final form, identical to the print version. [Has well over 450 notes/exercises, 200 detailed examples, 150 figures/tables, 600 references, 800 index entries].
See the special book page for details and availability.

Analytic Combinatorics proposes a unified treatment of analytic methods in combinatorics. We develop in about 800 pages the basics of asymptotic enumeration and the analysis of random combinatorial structures through an approach that revolves around generating functions and complex analysis. A symbolic framework (Chapters I-III) first provides systematically a large number of exact description of combinatorial models in terms of generating functions. Major properties of generating functions that are of interest in this book are singularities. The text then presents (in Chapters IV-VIII) the core of the theory with two chapters on complex analytic methods focusing on rational and meromorphic functions as well as two chapters on fundamentals of singularity analysis and combinatorial consequences, followed by a chapter on the saddle point method. The last section (Chapters IX) covers multivariate asymptotics and limit laws in random structures. Many examples are given that relate to words, integer compositions and partitions, paths and walks, graphs, mappings and allocations, lattice paths, permutations, trees, and planar maps.

• Multidimensional Divide-and-Conquer and Weighted Digital Sums (Extended Abstract). By Y. K. Cheung, Philippe Flajolet, Mordecai Golin, and C. Y. James Lee. In Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2009, pp. 58--65.

Yet another episode of the fact that divide-and-conquer algorithms, in either the worst-case or the average-case lead to recurrences whose solutions often have a fractal character. This paper studies two functions arising separately in the analysis of algorithms. The first function is the solution to the Multidimensional Divide-And-Conquer (MDC) recurrence that arises when solving problems involving points in d-dimensional space. The second function concerns weighted digital sums, which arise naturally in the analysis of binomial queues. See also below "Mellin Transforms and Asymptotics : The Mergesort Recurrence", by P. Flajolet, M Golin for the general methodology.

## 2008

• On Differences of Zeta Values. Philippe Flajolet and Linas Vepstas. In Journal of Computational and Applied Mathematics vol. 220:1-2 (2008), pp. 58--73. Available as arXiv:math/0611332.

Finite differences of values of the Riemann zeta function at the integers are explored. Such quantities, which occur as coefficients in Newton series representations, have surfaced in works of Maslanka, Coffey, Baez-Duarte, Voros and others. We apply the theory of Nörlund-Rice integrals in conjunction with the saddle point method and derive precise asymptotic estimates. The method extends to Dirichlet L-functions and our estimates appear to be partly related to earlier investigations surrounding Li's criterion for the Riemann hypothesis.

• Analytic Combinatorics of the Mabinogion Urn. Philippe Flajolet and Thierry Huillet. In Discrete mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AI, pages 549--572. Proceedings of Fifth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, September 22-26, 2008, Blaubeuren, Germany. U. Rösler editor. 23 pages.

The purpose of this paper is to introduce and study a simple model of the stochastic spread of influence in populations. Say a country consists of a population of N sheep, each of which can, at any given time, be in either one of two states of mind, denoted by A and B. At discrete instants 1,2,3,..., a randomly chosen sheep in the population bleats in accordance with its current state of mind: if this sheep bleats A[aah], then one of the B-sheep changes to state A; if this sheep bleats B[eeh], then one of the A-sheep changes to state B. The process stops when unanimity has been reached, that is, all sheep are in one and the same state. The problem is to determine the stopping time of the process as well as the probability that unanimity of either type is eventually reached, when given a certain initial condition of the population.

Where does this strange name comes from? It has been chosen by reference to the Welsh medieval epic tale, The Mabinogion, where one finds:

"And he came towards a valley, through which ran a river; and the borders of the valley were wooded, and on each side of the river were level meadows. And on one side of the river he saw a flock of white sheep, and on the other a flock of black sheep. And whenever one of the white sheep bleated, one of the black sheep would cross over and become white; and when one of the black sheep bleated, one of the white sheep would cross over and become black."

(Any resemblance to actual political events, past or present, is purely coincidental.)

## 2007

• HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm, by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Proceedings of the AofA07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127--146 (2007).

Contents: what the title says!!

• Boltzmann Sampling of Unlabelled Structures, by Philippe Flajolet, Éric Fusy, and Carine Pivoteau. In Proceedings of ANALCO'07 (Analytic Combinatorics and Algorithms) Conference, New Orleans, January 2007. SIAM Press, pp. 201--211.

Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of unlabelled objects. The resulting algorithms generate in an unbiased manner discrete configurations that may have nontrivial symmetries, and they do so by means of real-arithmetic computations. Here you'll find a collection of construction rules for such samplers, which applies to a wide variety of combinatorial classes, including integer partitions, necklaces, unlabelled functional graphs, dictionaries, series-parallel circuits, term trees and acyclic molecules obeying a variety of constraints.

• Analytic Combinatorics---A Calculus of Discrete Structures, by Philippe Flajolet. Invited lecture at the ACM-SIAM SODA Conference (Symposium on Discrete Algorithms), SIAM Press 2007, pp. 137--148.

The efficiency of many discrete algorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the geometry of the resulting functions. In this way, an operational calculus of discrete structures emerges. Applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.
Suresh's Geomblog has a perceptive description of the talk and its "message".

## 2006

• Some exactly solvable models of urn process theory. Philippe Flajolet, Philippe Dumas, and Vincent Puyhaubert. In Discrete Mathematics and Computer Science, vol. AG, pp. 59--118 (2006). Proceedings of Fourth Colloquium on Mathematics and Computer Science, Ph. Chassaing Editor.

An other episode of the analytic combinatorics saga. This time, we wanted to investigate the extent to which analytic methods can be applied to Pólya urn models ---the reader will have to decide by herself!

• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics. Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario, Nicolas Pouyanne. In Electronic Journal of Combinatorics, 13(1) R103, pp. 1--35 (November 2006).

A ``hybrid method'', dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions--this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.

• The Fermat cubic, elliptic functions, continued fractions, and a combinatorial excursion. Eric Conrad and Philippe Flajolet. Version of March 25, 2006 (with minor revisions). In Séminaire Lotharingien de Combinatoire (SLC) volume 54 (2006), 44 pages..

Elliptic functions considered by Dixon in the nineteenth century and related to Fermat's cubic (x^3+y^3=1), lead to a new set of continued fraction expansions with sextic numerators and cubic denominators. The functions and the fractions are pregnant with interesting combinatorics, including a special Pólya urn, a continuous-time branching process, as well as permutations satisfying constraints that involve either parity of levels of elements or a repetitive pattern of order three.

• The Ubiquitous Digital Tree, by Philippe Flajolet. Invited lecture at the annual Symposium on Theoretical Aspects of Computer Science, Marseille, February 2006. In STACS 2006, Volume 3884 of Lecture Notes in Computer Science, B. Durand and W. Thomas Ed., pp. 1-22.

• Hidden Word Statistics, Philippe Flajolet, Wojciech Szpankowski, and Brigitte Vallée. In Journal of the ACM, Volume 53:1, January 2006, pages 147--183.

Many people see hidden patterns, words, sentences, everywhere, with "Bible Codes" predicting the death of Lady D. and all sorts of things. See the intelligent discussion by Brendan McKay and his colleagues. Here, we show more modestly that hidden patterns (subsequences with or without limitations on the sizes of gaps) occur a number of times that is asymptotically Gaussian in a random large text. The method involve combinatorial descriptions by regular expresions and automata as well as asymptotic methods from analytic combinatorics (generating functions, singularities, moment convergence theorems, etc).
This journal version subsumes the earlier extended abstract: Hidden Pattern Statistics. P. Flajolet, Y. Guivarch, W. Szpankowski, B. Vallée. In Automata, Languages, and Programming (ICALP'2001), F. Orejas et al. Eds, Lecture Notes in Computer Science 2076, July 2001, pp. 152-165. [ps | pdf].

• The scientific works of Rainer Kemp (1949--2004). By Philippe Flajolet, Markus Nebel, and Helmut Prodinger. In Theoretical Computer Science, volume 355:3 (April 2006),pages 371--381.
Rainer Kemp, Professor of computer science at the Johann Wolfgang Goethe University of Frankfurt, passed away on May 14, 2004. In 32 years of academic scientific activity, Kemp wrote altogether 53 publications, of which a complete list appears in the bibliography section of this note. We analyse and organize into broad categories Kemp's papers of which we provide a complete list in the bibliography section of this note.
Kemp's research started with problems in the theory of formal languages, a by theng prevalent branch of computer science in Europe. He was especially interested in ``syntax analysis'' or parsing and, even after switching subjects, would return to formal languages every so often. However, soon after his beginnings, his interests started to drift towards discrete mathematics, especially combinatorial enumeration and asymptotic methods, with many of the problems he considered being motivated by analysis of algorithms. It is in this area that he published the vast majority of his papers.

• Fast Computation of Special Resultants. - Bostan (Alin), Flajolet (Philippe), Salvy (Bruno), and Schost (Éric). Journal of Symbolic Computation, Volume 41, Issue 1, Pages 1-29 (January 2006)

## 2005

• Analytic Urns, by Philippe Flajolet, Joaquim Gabarró, Helmut Pekari. In Annals of Probability, Volume 33(3), April 2005, pages 1200-1233.
A unified analytic solution for 2x2 urn models of the type considered by Pólya and many others, provided they have constant row sum. Contains elliptic functions, Abelian integrals over the Fermat curve (aargh!) and several other goodies.
Note. The original version (March 2003) had in addition some interesting examples involving stable laws and the Ehrensfest model ---these will be published separately later with Vincent Puyhaubert. See (momentarily): Analytic Urns, by Philippe Flajolet, Joaquim Gabarró, Helmut Pekari. March 1, 2003, 52 pages(!). [PS].
• On the non-holonomic character of logarithms, powers, and the nth prime function. Philippe Flajolet, Stefan Gerhold, and Bruno Salvy. Version of January 21, 2005. Appears in the Electronic Journal of Combinatorics, Volume 11(2), 2004-2005, pages A2:1--16.

Stanley, Zeilberger, Lipshitz, as well as a few others have revealed to the world of combinatorialists and special function specialists the beauty and power of the holonomic framework. (Synonym notions preferred by purists are P-recursiveness, for sequences, and D-finiteness for functions.) That day, we were on a negative-thinking mood, so that we decided to write down ideas drawn from a large body of very classical (and pure) maths, with which you can easily prove many sequences not to be holonomic.

• Singularity Analysis, Hadamard Products, and Tree Recurrences, by Jim Fill, Philippe Flajolet, and Nevin Kapur. In Journal of Computational and Applied Mathematics, volume 174 (February 2005), pages 271--313. [PS | PS.GZ].
This is yet another episode of the singular view of combinatorics. For a great many probabilistic models encountered in discrete math, singularities provide extremely precise and valuable information. Here, we look at some classical tree models (binary search trees, Catalan trees, union-find trees) but not so standard toll functions. In so doing, one has to cope with Hadamard products of generating functions. Fortunately, as shown here, functions amenable to singularity analysis are closed under Hadamard products. (Oh, by the way, what's a Hadamard product? Plainly, it's the termwise product of series.) A consequence of all this is the possibility of classifying the solution to several basic recurrences of the probabilistic divide-and-conquer type.

## 2004

• Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities. Series: Trends in Mathematics (Mathematics, Computer Science). Edited by Drmota, M.; Flajolet, P.; Gardy, D.; Gittenberger, B. 2004, XV, 554 p., Hardcover ISBN: 3-7643-7128-5 A Birkhäuser book.
• Boltzmann Samplers for the Random Generation of Combinatorial Structures, by Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer. In Combinatorics, Probability, and Computing, Special issue on Analysis of Algorithms, 2004, Vol. 13, No 4--5, pp. 577-625.
This paper received the 2007 Outstanding Simulation Publication Award of INFORMS, the Institute For Operations Research and the Management Sciences.
Why not use real numbers to draw at random large trees, words, permutations, graphs, etc, satisfying very diverse types of constraints? Here's the answer!
Subsumes Random Sampling from Boltzmann Principles. Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer. In Proc. ICALP'2002, Lecture Notes in Computer Science, vol 2380, July 2002, pp. 501-513.
• And/Or Trees Revisited. Brigitte Chauvin, Philippe Flajolet, Danièle Gardy, Bernhard Gittenberger. In Combinatorics, Probablity, and Computing, Special issue on Analysis of Algorithms, 2004, Volume 13, No 4--5, pp. 475-497. [ps | pdf].
We don't really understand complexity but we do understand probability. Can this help?
• Counting by coin tossings, by Philippe Flajolet. Version of 27 September 2004. Invited lecture at ASIAN'04 (the Ninth Asian Computing Science Conference held at Chiang Mai in December 2004). In Lecture Notes in Computer Science, vol 3321 (2004), M. Maher (Editor), pages 1--12. [PS]
A review of probabilistic counting algorithms for streams and massive data sets. You're much better off by flipping coins. This text also includes earlier invited lectures at ANALCO'04 (New Orleans, January 2004) and ICALP'04 (Turku, July 2004). See also some relevant slides under Theory and Practice of Probabilistic Counting Algorithms.
• Airy Phenomena and Analytic Combinatorics of Connected Graphs, Philippe Flajolet, Bruno Salvy, and Gilles Schaeffer. In Electronic Journal of Combinatorics, Volume 11(1), 2004, #R34, pp. 1-30. Published May 27, 2004. (The unfortunately uggly typography is theirs, not ours!) [ps | ps.gz].
How many connected graphs are there with a fixed excess of the number of edges over the number of nodes? This is a classical question, which is related to the problem of connectivity in random graphs of the Erdös-Renyi type. We revisit it under the radical angle of analysis, in accordance with what the title suggests: Airy functions, saddle points, even coalescing ones, and enumeration via divergent series make an appearance here.

## 2003

• Loglog Counting of Large Cardinalities, by Marianne Durand and Philippe Flajolet, 14 pages. In the "Engineering and Applications Track" of the 11th Annual European Symposium on Algorithms (ESA03). Proceedings published by Springer, Lecture Notes in Computer Science, vol 2832, pp.605-617. This document is dated September 2003. [PS | PS.GZ].
Using only memory equivalent to 5 lines of printed text, you can estimate with a typical accuracy of 5% and in a single pass the total vocabulary of Shakespeare. This wonderfully simple algorithm has applications in data mining, estimating characteristics of huge data flows in routers, etc. It can be implemented by a novice, can be fully parallelized with optimal speed-up and only need minimal hardware requirements. There's even a bit of math in the middle!
Note about successive versions. The official version [posted here January 1, 2004] subsumes the earlier version, dated April 1 2003, in which the algorithm's formulation was lacking a correction factor of 2. [PS | PDF].
• Hachage, Arbres, Chemins, et Graphes [in French]. by Philippe Chassaing and Philippe Flajolet. In Gazette des Mathématiciens vol. 95, pp.29-49, January 2003. [ps| pdf]
Traversing graphs, parking your car, storing your records in a file, walking back home loaded, and climbing trees to gather apples are all covered by the same mathematical theory.
Lightly adapted from a survey paper which was originally written for Bulletin du Laboratoire de Probabilités, Université Paris VI, June 2001, 17 pages. [ps| pdf]

### 2002

• Variations on Redundancy Rates of Renewal Processes. Philippe Flajolet and Wojtek Szpankowski. In IEEE Transactions on Information Theory 48(11), 2002, pp. 2911--2921.
• Motif Statistics [html], Nicodème (Pierre), Salvy (Bruno), and Flajolet (Philippe). Appears in Theoretical Computer Science 287:2, 2002, pages 593-617. [ps | ps.gz | pdf]

Extended abstract in European Symposium on Algorithms-ESA99, Lecture Notes in Computer Science 1643 (1999), pp. 194-211. The version offered here is: Research Report n°RR-3606, Institut National de Recherche en Informatique et en Automatique, January 1999.

• On the Robustness of Interconnections in Random Graphs: A Symbolic Approach. Philippe Flajolet, Kostas Hatzis, Sotiris Nikoletseas, and Paul Spirakis. In Theoretical Computer Science 287:2, 2002, pages 513-534.
A preliminary version is in IFIP International Conference on Theoretical Computer Science, Lecture Notes in Computer Science, vol. 1872, pp. 152-168.
• Analytic Combinatorics---Symbolic Combinatorics. Philippe Flajolet and Robert Sedgewick. 186p.+viii, May 2002. [PS(5.3Mb)| PDF(3.7Mb)]

This booklet develops in nearly 200 pages the basics of combinatorial enumeration through an approach that revolves around generating functions. The major objects of interest here are words, trees, graphs, and permutations, which surface recurrently in all areas of discrete mathematics. The text presents the core of the theory with chapters on unlabelled enumeration and ordinary generating functions, labelled enumeration and exponential generating functions, and finally multivariate enumeration and generating functions. It is largely oriented towards applications of combinatorial enumeration to random discrete structures and discrete mathematics models, as they appear in various branches of science, like statistical physics, computational biology, probability theory, and, last not least, computer science and the analysis of algorithms.
Symbolic Combinatorics is a set of lecture notes that are a component of a wider book project titled Analytic Combinatorics, which will provide a unified treatment of analytic methods in combinatorics. This text is partly based on an earlier document titled ``The Average Case Analysis of Algorithms: Counting and Generating Functions'', INRIA Res. Rep. #1888 (1993), 116 pages, which it now subsumes.

• Singular Combinatorics. Philippe Flajolet. In Proceedings of the International Congress of Mathematicians 2002, vol III, World Scientific, 2002, pp. 561--571. (Invited lecture at ICM02, Beijing, August 2002.) [ps| pdf]
• Basic Analytic Combinatorics of Directed Lattice Paths. by Cyril Banderier and Philippe Flajolet. In Theoretical Computer Science 281:1-2 (2002), pp. 37-80. [ps| pdf]
• Generating Functions of Generating Trees. Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, Dominique Gouyou-Beauchamps. In Discrete Mathematics 246(1-3), March 2002, pp. 29-55. [ps| pdf]
The version posted here is the Report ALCOM FT-TR-01-17 (February 2001) of the Alcom-FT Project of the E.U.
This replaces the earlier conference version: On Generating Functions of Generating Trees, INRIA Research Report RR-3661, April 1999, 13 pages. In Proceedings of Formal Power Series and Algebraic Combinatorics (FPSAC'99), Barcelona, June 1999. [ps | pdf]

### 2001 (Happy New Millennium to all!)

• Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena. Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michele Soria. In Random Structures and Algorithms 19(3-4), 2001, pp 194--246.
An extended abstract version has previously appeared. See: Planar Maps and Airy Phenomena (280k). Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria. In Automata, Languages, and Programming, volume 1853 of Lecture Notes in Computer Science, pp. 388-402. (Proceedings of ICALP'2000, Geneva, July 2000.) [ps, 1046k]
• Analytic Variations on the Airy Distribution. Philippe Flajolet and Guy Louchard. In Algorithmica 31 2001 (Special issue on Analysis of Algorithms), pp. 361--377.

The Airy distribution (of the "area" type) occurs as a limit distribution of cumulative parameters in a number of combinatorial structures, like path length in trees, area below walks, displacement in parking sequences, and it is also related to basic graph and polyomino enumeration. We obtain curious explicit evaluations for certain moments of the Airy distribution, including moments of orders -1, -3, -5, etc., as well as +1/3, -5/3, -11/3, etc, and -7/3, -13/3, -19/3, etc. Our proofs are based on integral transforms of the Laplace and Mellin type and they rely essentially on non-probabilistic arguments like analytic continuation. A byproduct of this approach is the existence of relations between moments of the Airy distribution, the asymptotic expansion of the Airy function Ai(z) at +infinity, and power symmetric functions of the zeros of Ai(z).

• The complete analysis of a polynomial factorization algorithm over finite fields. P. Flajolet, X. Gourdon, and D. Panario. In Journal of Algorithms 40, 2001, pp. 37-81. [ps | pdf].
• Dynamical Sources in Information Theory: A General Analysis of Trie Structures, J. Clément, P. Flajolet, B. Vallée. In Algorithmica 29(1/2), 2001, pp. 307-369. (Preliminary version available here is INRIA Research Report RR-3645, March 1999, 61 pages.) [ps | pdf]