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.

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.

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

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.

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.
  See my Books page for details.
• 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].
  An extended abstract version, Random Polynomials and Polynomial Factorization , has appeared in Proc. 23rd ICALP Conference, 1996, Lecture Notes in Computer Science. vol. 1099, F. Meyer auf der Heide Ed., pp. 232-243.
• 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]

• Continued Fractions, Comparison Algorithms, and Fine Structure Constants. Philippe Flajolet and Brigitte Vallée. In "Constructive, Experimental, and Nonlinear Analysis", M. Théra Ed., (CMS Conf. Proc., 27, Amer. Math. Soc., Providence), pp. 53-82. (Volume in the honour of Jonathan Borwein.) This is a preliminary version as INRIA Research Report 4072, 2000. [ps].
• The Formal Theory of Birth-and-Death Processes, Lattice Path Combinatorics, and Continued Fractions (145kb), Philippe Flajolet and Fabrice Guillemin. In Advances in Applied Probability 32(3), 2000, pp. 750-778. Preliminary version as INRIA Research Report RR-3667, April 1999, 23 pages. [ps | pdf]
• Analytic Variations on Bucket Selection and Sorting (121kb), Hosam Mahmoud, Philippe Flajolet, Philippe Jacquet, and Mireille Régnier. In Acta Informatica 36(9-10), 2000, pp. 735-760. The preliminary form available here is INRIA RR3399, April 1998, 22 pages. [ps]
• Analytic Combinatorics of Chord Diagrams (261k). Philippe Flajolet and Marc Noy, Appears in Formal Power Series and Algebraic Combinatorics, 2000, pp. 191-201 (D. Krob, A. A. Mikhalev, A. V. Mikhalev Editors; Springer Verlag. Proc. of FPSAC'2000, June 2000, Moscow). The form available here is INRIA RR3914, March 2000. [ps | pdf]]

  1999

• Analytic Combinatorics of Non-crossing Configurations (146kb), P. Flajolet, M. Noy. In Discrete Mathematics 204(1-3), 1999, 203-229 (Selected papers in honor of Henry W. Gould). The version available here is a preliminary version: INRIA RR3196, June 1997. 22 pages. [ps]
• Properties of Random Triangulations and Trees [abstract]. L. Devroye, P. Flajolet, F. Hurtado, M. Noy, W. Steiger. In Discrete and Computational Geometry 22, pp. 105-117 (1999) Subscribers to Springer's service may view the full text in pdf.
• Stirling Numbers for Complex Arguments and Hankel Contours (HTML with gif pages). Philippe Flajolet, Helmut Prodinger. SIAM Journal on Discrete Mathematics 12:2, 1999, pp. 155-159. The preliminary version offered here is INRIA Report RR3373, March 1998, 5 pages [ps.gz | ps]
• Singularity analysis and asymptotics of Bernoulli sums, Philippe Flajolet. In Theoretical Computer Science 215(1-2), 1999, pp. 371--381. The form available here is INRIA RR3401, April 1998, 10 pages. [ps]

  1998

• On the Analysis of Linear Probing Hashing Philippe Flajolet, Patricio Poblete, and Alfredo Viola In Algorithmica 22, (December 1998), pp. 490-515. (Special Issue on Analysis of Algorithms.)
• Euler Sums and Contour Integral Representations. P. Flajolet and B. Salvy. In Journal of Experimental Mathematics, volume 7(1), 1998, pp. 15-35, where it is available electronically freely by courtesy of the publisher.
• Continued Fraction Algorithms, Functional Operators, and Structure Constants (148kb), P. Flajolet and B. Vallée. The full paper appears in Theoretical Computer Science, March 1998, vol 194 (1-2), pp. 1-34. Here is a preliminary version (INRIA, RR2931, July 1996. 33 pages) that is the text of an invited lecture at the 7th conference "Fibonacci Numbers and Applications", Graz, July 1996.
• The Analysis of Hybrid Trie Structures , Julien Clément, Philippe Flajolet, Brigitte Vallée. In Proceedings of the Ninth ACM_SIAM Symposium on Discrete Algorithms (SODA'98), San Francisco, January 1998, pp. 531-539.
• The Maximum of a Random Walk and Its Application to Rectangle Packing (98kb), E.~G.~Coffman, Philippe Flajolet, Leopold Flatto, and Micha Hofri. In Probability in Engineering and Informational Sciences, 12 (1998), pp. 373-386. The form available here is (INRIA, RR3223), July 1997. 14 pages. [ps]

  1997

• An average-case analysis of the Gaussian algorithm for lattice reduction (132kb), H. Daudé, P. Flajolet, and B. Vallée. In Combinatorics, Probability and Computing 6 (4), 1997, pp. 397-433. (Preliminary version available here: INRIA, RR 2798, February 1996.)
• The SIGSAM Challenges: Symbolic Asymptotics in Practice. Philippe Flajolet and Bruno Salvy. In SIGSAM Bulletin, vol 31 (4), 1997, pages 36-47.
• Patterns in Random Binary Search Trees (104kb), P. Flajolet, X. Gourdon, C. Martinez. (INRIA, RR2997), October 1996. 23 pages. Final version appears in Random Structures and Algorithms, volume 11 (3), October 1997, pp. 223-244.
• Adaptive Sampling. Philippe Flajolet. In Encyclopaedia of Mathematics, M. Hazewinkel Editor (1997). In Suppl. I, p. 28.
  Nice! The whole collection of articles in the Encyclopaedia of Mathematics has now been made freely available by Springer Verlag at their site: http://eom.springer.de/.

  1996

• Zeta Function expansions of Classical Constants. Philippe Flajolet and Ilan Vardi. This is the current edition of an unpublished memo that was devopped around 1990-1992 and has been circulated around for a while.
• Random Triangulations [Extended Abstract] (138kb), L. Devroye, P. Flajolet, F. Hurtado, M. Noy, and W. Steiger, 2852), April 1996. 10 pages. Accepted for publication in Discrete and Computational Geometry.
• Asymptotique des récurrences mahleriennes: le cas cyclotomique, P. Dumas, P. Flajolet, Journal de Théorie des Nombres de Bordeaux 8(1), 1996, pp. 1-30. Available from the wonderful NUMDAM Site.
  Some tricky analysis meant to elucidate things including the asymptotics number of partitions into powers of two (binary partitions), following the lead of N. G. de Bruijn.

  1995

• Computer Algebra Libraries for Combinatorial Structures, Philippe Flajolet and B. Salvy. In Journal of Symbolic Computation, vol 20, 1995, pp. 653-671.
• Hypergeometrics and the Cost Structure of Quadtrees, Philippe Flajolet, Gilbert Labelle, Louise Laforest and B. Salvy. In Random Structures and Algorithms , vol. 7 (2), 1995, pp. 117-144.
• Mellin Transforms and Asymptotics : Harmonic Sums, P. Flajolet, X. Gourdon, P. Dumas. In Theoretical Computer Science , vol. 144 (1-2), 1995, pp. 3-58. There is also a list of Corrigenda, updated in 2004.
• Mellin Transforms and Asymptotics : Finite Differences and Rice's Integrals, P. Flajolet, R. Sedgewick. In Theoretical Computer Science , vol. 144 (1-2), 1995, pp. 101-124.
• On Ramanujan's Q-function, P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger. In J. Computational and Applied Mathematics, vol. 58 (1), 1995, pp. 103-116.

  1994

• Mellin Transforms and Asymptotics : The Mergesort Recurrence, P. Flajolet, M Golin. In Acta Informatica , vol. 31, 1994, pp. 673-696.
  Subsumes Exact asymptotics of divide--and--conquer recurrences. In Automata, Languages, and Programming (ICALP'93). Lecture Notes in Computer Science vol 700, pp. 137-149.
• Mellin Transforms and Asymptotics : Digital Sums, P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, R. Tichy. In Theoretical Computer Science, vol. 123 (2), 1994, pp. 291-314.
• A Calculus for the Random Generation of Labelled Combinatorial Structures(362kb), P. Flajolet, P. Zimmermann, B. Van Cutsem, In Theoretical Computer Science, vol. 132 (1-2), 1994, pp. 1-35. [pdf]
• Search Costs in Quadtrees and Singularity Perturbation Asymptotics , P. Flajolet, Thomas Lafforgue. In Discrete and Computational Geometry, vol 12 (4), 1994, pp. 151-175.

  1993

• Analytic Variations on Quadtrees. Philippe Flajolet, Gaston Gonnet, Claude Puech and J. M. Robson. In Algorithmica 10:7, pp. 473-500, December 1993.
• The distribution of heights of binary trees and other simple trees. P. Flajolet, Z. Gao, A. Odlyzko, and B. Richmond. In Combinatorics, Probability, and Computing, vol 2 (1993), pp. 145-156.
• General Combinatorial Schemas: Gaussian Limit Distributions and Exponential Tails, P. Flajolet, M. Soria. In Discrete Mathematics, , vol 114, 1993, pp. 159--180.

  1992

• Analytic Analysis of Algorithms (378kb). Philippe Flajolet. Invited lecture given at the 19th International Colloquium ICALP'92, Vienna, July 1992. Proceedings published as Automata, Languages and Programming, in Lecture Notes in Computer Science Vol. 623, W. Kuich Editor (1992), pp 186--210. [ps (2727kb)]
• Varieties of Increasing Trees. F. Bergeron, P. Flajolet, and B. Salvy. In Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992. Proceedings published in Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, pp. 24-48.
  This paper is an extended abstract that was presented at the last issue of the series of conferences on trees in computer science (CAAP). There, we consider increasing trees, which are labelled trees where node labels go in increasing order along any branch stemming from the root. We allow for various sorts of rules: for instance the trees may be "planar" (i.e., given together with an embedding in the plane) or not, they may be binary, or "general" (i.e., any node degree is allowed). This covers a number of models that have surfaced here and there in cmputer science as well as in probability theory. For instance, the binary planar case is isomorphic to binary search trees; the geneal nonplane case gives rise to what Meir and Moon strangely called recursive trees (but aren't all tree structures recursive?), and the model would surface again, a few years later, as a simple model of acquaintance networks, while probabilists would view it more or less as an instance of the Chinese restaurant problem, etc. Problems in this area had been so far treated by a variety of methods, like elementary combinatorics, recurrences, probabilistic methods (e.g., martingales) and urn models (cf Mahmoud and coauthors). In our paper, we provide a unified theory of increasing tree models based on generating functions (of course!), singularity analysis, as well as singularity perturbation. This makes it possible to derive mean, variance, and sometimes limit distribution estimates for many parameters including: root-degree, number of leaves or of nodes of any fixed degree, level distribution, path length, and so on.

• Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-organizing Search, Discrete Applied Mathematics 39 (1992), 207--229.
  A unified framework for the problems listed in the title; not too surprisingly based on ... generating functions.

• Page Usage in a Quadtree Index, M. Hoshi, P. Flajolet. In BIT,, vol 32, 1992, pp. 384-402.
• Generalized Digital Trees and Their Difference--differential Equations, P. Flajolet, B. Richmond. In Random Structures and Algorithms,, vol 3 (3), 1992, pp. 305-320.

  1991

• Automatic average-case analysis of algorithms P. Flajolet, B. Salvy, and P. Zimmermann. In Theoretical Computer Science, vol. 79, no. 1, 1991, pp. 37-109.
• The Cycle Construction (19kb), P. Flajolet, M. Soria. In SIAM J. Discr. Math., , vol 4 (1), 1991, pp. 58-60.
• Polya Festoons, P. Flajolet. In INRIA Research Report, No 1507, September 1991. 6pp.

  1990

• Average-Case Analysis of Algorithms and Data Structures, by J. S. Vitter and Ph. Flajolet. Chapter 9 in Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (edited by J. van Leeuwen), Elsevier, 1990, 431-524. (The version offered here is without figures.)
• Analytic Variations on the Common Subexpression Problem, , P. Flajolet, P. Sipala, and J-M. Steyaert, In Proceedings of the 17th ICALP Conference, Warwick, July 1990. Lecture Notes in Computer Science, Vol. 443, pp. 220-234.
• Gaussian Limiting Distributions for the Number of Components in Combinatorial Structures (57kb). P. Flajolet, M. Soria. In J. Combinatorial Theory, Series A, , vol 53, 1990, pp. 165-182.
• Singularity analysis of generating functions. P. Flajolet and A. M. Odlyzko. In SIAM J. Discrete Math., vol 3 (1990) pp. 216-240.
• Random Mapping Statistics (175kb), P. Flajolet, A. Odlyzko. In Advances in Cryptology, Proc. Eurocrypt'89, , J-J. Quisquater Ed., Lect. Notes in Comp. Sc. vol 434, 1990, pp. 329-354.
• Non-overlapping Partitions, Continued Fractions, Bessel Functions and a Divergent Series , P. Flajolet and R. Schott. In European Journal of Combinatorics, Vol 11, 1990, pp. 412-432. [ps|ps.gz]
• On adaptive sampling. P. Flajolet. In Computing, Vol 34, 1990, pp. 391-400.

  ---

  Prehistory (before 1990)

• Elliptic Functions, Continued Fractions and Doubled Permutations. By Philippe Flajolet and Jean Francon. In European Journal of Combinatorics vol 10 (1989), pp. 235-241.
• Lambda-Upsilon-Omega the 1989 cookbook (INRIA RR 1073) P. Flajolet, B. Salvy, and P. Zimmermann, 1989.
• Deviations from uniformity in random strings. By Flajolet, Philippe, Kirschenhofer, Peter and Tichy, Robert F.. In Probability Theory and Related Fields, 1988, vol 80, 139--150.
  
  Almost all strings of size n contain all blocks of size (1-ε)lg(n) a close to uniform number of times. This paper presents quantitative refinements of this assertion based on the notion of discrepancy as well as on explicit generating function expressions for pattern occurrences (a la Guibas-Odlyzko) combined with the saddle point method.
• Random Tree Models in the Analysis of Algorithms. By Philippe Flajolet. Invited lecture at the PERFORMANCE'87 Conference, Brussels, 1988. Proceedings published by Elsevier Science Publishers (North Holland), P.-J. Courtois and G. Latouche Editors., pp. 171--187.
• Mathematical Methods in the Analysis of Algorithms and Data Structures. Philippe Flajolet. In Trends in Theoretical Computer Science, Chapter VI, Computer Science Press, 1988, E. Börger Editor. Pages 225--304. (Lecture Notes for A Graduate Course in Computation Theory, Udine, 1984)
  Probably by now mostly of historical interest. Look up Vitter & Flajolet (1990) or Sedgewick & Flajolet (1996) for more on analysis of algorithms. Refer to the book Analytic Combinatorics by Flajolet & Sedgewick (2007) for deeper connections between combinatorics and analysis.

• Evaluation de protocoles de communications: Aspects mathematiques (98kb). This document (in French) corresponds to a plenary lecture at the Annual Meeting of Societe Mathematique de France. January 1988. (Some figures missing.) [ps]
• Analytic Models and Ambiguity of Context-Free Languages, by Philippe Flajolet. In Theoretical Computer Science, 49, 1987, pp. 283--309. {Scanned PDF with OCR.]
• Level number sequences for trees, by Flajolet, Philippe and Prodinger, Helmut. In Discrete Mathematics 65, 1987, pp. 149--156.
• Analytic models for tree communication protocols. by P. Flajolet and P. Jacquet. In A. R. Odoni, L. Bianco, and G. Szegö, editors, Flow Control of Congested Networks, volume 38 of NATO Advance Science Institute Series. Series F: Computer and Systems Sciences, pages 223-234. Springer Verlag, 1987. (Invited Lecture).
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. Albert G. Greenberg, Philippe Flajolet and Richard E. Ladner; Journal of the ACM 34, 2 (Apr. 1987), Pages 289-325 (full text for subscribers of ACM's digital library) .
• Digital Search Trees Revisited. Philippe Flajolet and Robert Sedewick. In SIAM Journal on Computing 15:3, pp. 748--767.
  How to analyse digital trees (aka "tries"), Patricia trees, and especially digital search trees. Presents the first(?) unified view of analyses by generating functions, Mellin transforms, and so-called Rice integrals.
• On a Functional Equation Arising in the Analysis of a Protocol for a Multi-Access Broadcast Channel. Guy Fayolle, Philippe Flajolet, and Micha Hofri. In Advances in Applied Probability vol 18 (1986), pp. 441--472.
  Contains (the sketch of) what seems to be the first discussion of periodic/aperiodic error terms in expected value estimates of parameters of tries (aka "digital trees"). This is the (in)famous logp/logq criterion for a binary memoryless source. The characteristic equation p^s+q^s=1 (in s complex, with p+q=1) is central. Also, the non-local character of the functional equation (which is due to "continuous arrivals") distinguishes it from usual functional equations that arise in trie theory, since the later are purely local around 0. The latter aspect seems to be related to a special case of what would nowadays be called an IFS (Iterative Function System).
  The evolution of two stacks in bounded space and random walks in a triangle. Philippe Flajolet. Mathematical Foundations of Computer Science, in Lecture Notes in Computer Science 233, (1986).J. Gruska et al. Eds, Pages 325--340.
  What is the power of memory sharing for two evolving stacks, each subjected to random insertions and deletions? The question was posed as an open problem by Knuth in 1968 (cf Ex. 2.2.2.13 of The Art of Computer Programming). Here is a complete analytic solution that involves Chebyshev polynomials and continued fractions, shuffle products, as well as miscellaneous asymptotics.
• Partial match retrieval of multidimensional data. Philippe Flajolet and Claude Puech. Journal of the ACM, Volume 33, Issue 2 (1986). Pages 371-407.
  Binary search tree are imperfectly balanced trees that allow for efficient retrieval of one-dimensional data. In the multidimensional case, which is of interest in computational geometry, we have k-d-trees and quadtrees. Here we showed that, as a consequence of their partial imbalance, the cost of a partial match query in a 2-d-trees is asymptotically higher than what would happen in a perfect tree. The analysis involves studying singularities of linear differential systems satisfied by the corresponding generating functions. It reveals the surprising occurrence of exponents in asymptotic expansions that are algebraic numbers (for instance $sqrt(17)$) for 1/2d search. The functions involved are by now recognized as belonging to the holonomic framework. The asymptotic methods, based on singularity analysis, are of considerable generality in this context and in the study of probabilistic divide-and-conquer recurrences.
• The Analysis of Simple List Structures. By Flajolet, Philippe and Puech, Claude and Vuillemin, Jean. In Information Sciences 1986, pages 121--146, Volume 38.
  This is yet another episode of the continued fraction saga. We show that variances (and in principle higher moments) of various histories, that is, "weighted path diagrams", can be analysed exactly, thanks to orthogonality properties of various q-analogues of classical orthogonal polynomials (including Laguerre and Hermite). Caveat: something got wrong in the case of dictionary, where our Macsyma supported computations erred; this was to be repaired later by Guy Louchard's nice probabilistic treatment, which is in terms of Gaussian processes and Brownian motion.
• Q-ary collision resolution algorithms in random-access systems with free or blocked channel access. Peter Mathys and Philippe Flajolet. Invited paper in IEEE Transactions on Information Theory, vol 31:2, pp. 217-243.
  By changing binary branching to ternary branching, you can achieve a 40% throughput rate with the Capetanakis-Tsybakov-Mikhailov protocol. This is supported by a thorough analysis, and the protocol is easy to implement and robust.
• Probabilistic Counting Algorithms for Data Base Applications. Philippe Flajolet and G. Nigel Martin. In Journal of Computer and System Sciences, vol 31(2), 1985, pp. 182-209.
  This is a cute probabilistic algorithm for estimating the number of distinct elements in a large file using very little memory. It was originally designed for data base query optimization but, together with its descendants, it has found many applications for flow couting in routers and data mining. See CiteSeer for [FlMa83] and CiteSeer for [FlMa85] for uses like data mining on the internet graph, approximate query answering in very large data bases, virus detection in routers, etc.
  Subsumes: P. Flajolet, G. Martin. Probabilistic Counting. In Proc. 24th Symposium on Foundations of Computer Science, 1983, pages 76-82.
  See above: Loglog Counting of Large Cardinalities, by Marianne Durand and Philippe Flajolet, 2003, for an even more efficient algorithm, and the Year 2006 for the further improvement(!) HyperLogLog..
• Approximate Counting: A Detailed Analysis [pdf]. Philippe Flajolet. In BIT vol 25 (1985), pp. 113-134.
  How far can you count on your ten fingers? Well, during the Stone Age, it was until 10. During the Numeric Age, till 1024. But do you know that, once equiped with a source of randomness, you can count the number of particles in the universe (some say the number is about $10^70$) with an accuracy of about 20%? This article will tell you how! Indeed, a cute algorithm of Morris, analysed very precisely here, enables you to maintain an approximate counter till logN only requiring log(logN) bits. The results also describe the delay incurred by an Ethernet packet conditioned upon the number of collisions. In the 2000s, the same distribution has surfaced in the analysis of the TCP protocol (by Guillemin, Robert, and Zwart) and in exponential functionals of Poisson processes (by Bertoin, Biane, and Yor).
• Algebraic Methods for Trie Statistics. By Flajolet, Philippe and Régnier, Mireille and Sotteau, Dominique. In Annals of Discrete Mathematics 25, pp. 145--188. (From Proceedings of Analysis and Design of Algorithms for Combinatorial Problems, G. Ausiello and M. Lucertini Editors.)
• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumeration. (59kb) P. Flajolet and A. M. Odlyzko. In Math. Proc. Cambridge Phil. Soc., 96 (1984). pp. 237-253.
• On congruences and continued fractions for some classical combinatorial quantities. Philippe Flajolet. In Discrete Mathematics 41 (1982), no. 2, 145-153.
• The Average Height of Binary Trees and Other Simple Trees". Philippe Flajolet and Andrew Odlyzko. In Journal of Computer and System Scienes, vol 25, 1982, pp. 171-213.
• A Recursive Partitioning Process of Computer Science. By Philippe Flajolet and Dominique Sotteau. In Second World Conference on Mathematics at the Service of Man, Las Palmas, Canary Islands, Spain, 1982, pages 25--30.
• Dynamic Data Structures: Fiite Files, Limiting Profiles and Variance Analysis. Chéno, Laurent, Flajolet, Philippe, Françon, Jean, Puech, Claude, and Vuillemin, Jean. In Proceedings of the Eighteenth Annual Conference on Communication, Control, and Computing. October 1980, Allerton, IL, pp. 223--232.
  Summarizes an early treatment of the Ehrenfest urn model by continued fractions [read between lines!], shows the existence of a "mean"limiting profile of "histories" [Guy Louchard would considerably improve these results a few years later!], and presents a calculus of variance based on q-analogues of Hermite, Laguerre polynomials [see our later 1986 paper].
• Sequence of Operations Analysis for Dynamic Data Structures. Philippe Flajolet, Jean Françon, Jean Vuillemin. Journal of Algorithms 1, pp. 111-141.
  This paper analyses the total [called here "integrated"] cost of managing structures that evolve under the effect of random insertions, deletions, and queries. In essence, all evolutions of a given length are taken here with equal likelihood. The tools used are algebraic continued fractions, orthogonal polynomials, and special functions. An integral transform is explicitly computed for each basic policy and is related to a family of continued fraction expansions and special polynomials (Hermite, Laguerre, Charlier, Meixner).ß
• Combinatorial Aspects of Continued Fractions (2.4Mb). Philippe Flajolet. In Discrete Mathematics 32 (1980), pp. 125-161. A classic (!) now available in digitized form (with OCR and search!). Reprinted in the 35th Special Anniversary Issue of Discrete Mathematics, Volume 306, Issue 10--11, Pages 992-1021 (2006).

To obtain copies of other works or paper copy, please contact me.
Technical comments are also most welcome!

Return to Philippe Flajolet's Home Page

Philippe.Flajolet@inria.fr