This version of September 2010 subsumes the earlier extended abstract:
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.
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.
Where does this strange name comes from? It has been chosen by reference to the Welsh medieval epic tale, The Mabinogion, where one finds:
(Any resemblance to actual political events, past or present, is purely coincidental.)
Contents: what the title says!!
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.
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".
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 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.
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.
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].
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
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.
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.