Analytic combinatorics: a calculus of discrete structures

ABSTRACT

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.

REFERENCES

• 1: D.J. Aldous, Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels, IEEE Transactions on Information Theory, v.33 n.2, p.219-223, March 1987 [doi>10.1109/TIT.1987.1057295]
• 2: Edward A. Bender, Zhicheng Gao, and Nicholas C. Wormald. The number of labeled 2-connected planar graphs. Electronic Journal of Combinatorics, 9(1):Research Paper 43, 13 pp., 2002.
• 3: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures. Cambridge University Press, Cambridge, 1998.
• 5: Arthur W. Burks, Herman H. Goldstine, and John von Neumann. Preliminary discussion of the logical design of an electronic computing instrument. Report to the U.S. Army Ordnance Department, 1946. Reprinted in Computer Structures: Readings and Examples, C. Gordon Bell and Allen Newell editors, McGraw-Hill, 1971, pp. 92--119.
• 6: L Devroye, Branching processes in the analysis of the heights of trees, Acta Informatica, v.24 n.3, p.277-298, June 1987
• 7: Michael Drmota, Systems of functional equations, Random Structures & Algorithms, v.10 n.1-2, p.103-124, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.0.CO;2-Z]
• 8: Michael Drmota. An analytic approach to the height of binary search trees. Algorithmica, 29:89--119, 2001.
• 9: Amalia Duch , Vladimir Estivill-Castro , Conrado Martinez, Randomized K-Dimensional Binary Search Trees, Proceedings of the 9th International Symposium on Algorithms and Computation, p.199-208, December 14-16, 1998
• 10: Philippe Duchon , Philippe Flajolet , Guy Louchard , Gilles Schaeffer, Boltzmann Samplers for the Random Generation of Combinatorial Structures, Combinatorics, Probability and Computing, v.13 n.4-5, p.577-625, July 2004 [doi>10.1017/S0963548304006315]
• 11: Marianne Durand and Philippe Flajolet. LOGLOG counting of large cardinalities. In G. Di Battista and U. Zwick, editors, Annual European Symposium on Algorithms (ESA03), volume 2832 of Lecture Notes in Computer Science, pages 605--617, 2003.
• 12: James Allen Fill , Philippe Flajolet , Nevin Kapur, Singularity analysis, Hadamard products, and tree recurrences, Journal of Computational and Applied Mathematics, v.174 n.2, p.271-313, 15 February 2005 [doi>10.1016/j.jcam.2004.04.014]
• 13: James Allen Fill and Svante Janson. The number of bit comparisons used by quicksort: An average-case analysis. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA04), pages 293--300, 2001.
• 14: P. Flajolet, Analytic models and ambiguity of context-free languages, Theoretical Computer Science, v.49 n.2-3, p.283-309, January 1987 [doi>10.1016/0304-3975(87)90011-9]
• 15: Philippe Flajolet, Éric Fusy, and Carine Pivoteau. Boltzmann sampling of unlabelled structures. Preprint. Submitted to Analco'07, New-Orleans, 14 pages.
• 16: Philippe Flajolet , Mordecai Golin, Mellin transforms and asymptotics, Acta Informatica, v.31 n.7, p.673-696, Oct. 1994 [doi>10.1007/BF01177551]
• 17: Philippe Flajolet, Gaston Gonnet, Claude Puech, and J. M. Robson. Analytic variations on quadtrees. Algorithmica, 10(7):473--500, December 1993.
• 18: P. Flajolet , X. Gourdon , D. Panario, The complete analysis of a polynomial factorization algorithm over finite fields, Journal of Algorithms, v.40 n.1, p.37-81, July 2001 [doi>10.1006/jagm.2001.1158]
• 19: Philippe Flajolet, Patricio Poblete, and Alfredo Viola. On the analysis of linear probing hashing. Algorithmica, 22(4):490--515, December 1998.
• 20: Philippe Flajolet , Bruno Salvy , Paul Zimmermann, Automatic average-case analysis of algorithms, Theoretical Computer Science, v.79 n.1, p.37-109, Feb. 21, 1991 [doi>10.1016/0304-3975(91)90145-R]
• 21: Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. April 2006. Chapters I-IX of a book to be published by Cambridge University Press, 717p.+x, available electronically from P. Flajolet's home page.
• 22: Philippe Flajolet , Wojciech Szpankowski , Brigitte Vallée, Hidden word statistics, Journal of the ACM (JACM), v.53 n.1, p.147-183, January 2006 [doi>10.1145/1120582.1120586]
• 23: Philippe Flajolet and Brigitte Vallée. Continued fractions, comparison algorithms, and fine structure constants. In Michel Théra, editor, Constructive, Experimental, and Nonlinear Analysis, volume 27 of Canadian Mathematical Society Conference Proceedings, pages 53--82, Providence, 2000. American Mathematical Society.
• 24: Philippe Flajolet , Paul Zimmerman , Bernard Van Cutsem, A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, v.132 n.1-2, p.1-35, Sept. 26, 1994 [doi>10.1016/0304-3975(94)90226-7]
• 25: Éric Fusy. Quadratic exact-size and linear approximate-size random generation of planar graphs. Discrete Mathematics & Theoretical Computer Science Proceedings, AD:125--138, 2005.
• 26: Ira M. Gessel, Symmetric functions and P-Recursiveness, Journal of Combinatorial Theory Series A, v.53 n.2, p.257-285, Mar. 1990 [doi>10.1016/0097-3165(90)90060-A]
• 27: Omer Giménez and Marc Noy. The number of planar graphs and properties of random planar graphs. Discrete Mathematics and Theoretical Computer Science Proceedings, AD:147--156, 2005.
• 28: Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison Wesley, 1989.
• 29: Doug Hensley. The number of steps in the Euclidean algorithm. Journal of Number Theory, 49(2):142--182, 1994.
• 30: Micha Hofri, Analysis of algorithms: computational methods and mathematical tools, Oxford University Press, Oxford, 1995
• 31: Hsien-Kuei Hwang, On convergence rates in the central limit theorems for combinatorial structures, European Journal of Combinatorics, v.19 n.3, p.329-343, April 1, 1998 [doi>10.1006/eujc.1997.0179]
• 32: Philippe Jacquet , Wojciech Szpankowski, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, Theoretical Computer Science, v.144 n.1-2, p.161-197, June 26, 1995 [doi>10.1016/0304-3975(94)00298-W]
• 33: Peter Kirschenhofer and Helmut Prodinger. On some applications of formulæ of Ramanujan in the analysis of algorithms. Mathematika, 38:14--33, 1991.
• 34: Donald E. Knuth. The Art of Computer Programming. Addison-Wesley, 1968--73. 3 volumes: Fundamental Algorithms, Seminumerical Algorithms, Sorting and Searching.
• 35: Guy Louchard and Wojciech Szpankowski. On the averagee redundancy rate of the Lempel-Ziv code. IEEE Transactions on Information Theory, 43(1):2--8, 1997.
• 36: Hosam M. Mahmoud. Evolution of Random Search Trees. John Wiley, New York, 1992.
• 37: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 38: Pierre Nicodème , Bruno Salvy , Philippe Flajolet, Motif statistics, Theoretical Computer Science, v.287 n.2, p.593-617, 28 September 2002 [doi>10.1016/S0304-3975(01)00264-X]
• 39: Albert Nijenhuis and Herbert S. Wilf. Combinatorial Algorithms. Academic Press, second edition, 1978.
• 40: A. M. Odlyzko, Asymptotic enumeration methods, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
• 41: Robin Pemantle and Mark C. Wilson. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. Preprint, dec 2005. Arxiv:math.CO/0512548, 89 pages.
• 42: G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68:145--254, 1937.
• 43: Kenneth P. Bogart, Introductory Combinatorics, Pitman Publishing, Inc., Marshfield, MA, 1983
• 44: Michael O. Rabin. Probabilistic algorithms. In J. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 21--39, New York, 1976. Academic Press.
• 45: Gilles Schaeffer, Random sampling of large planar maps and convex polyhedra, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.760-769, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301448]
• 46: Robert Sedgewick. Algorithms in C, Parts 1--4. Addison-Wesley, Reading, Mass., third edition, 1998.
• 47: Robert Sedgewick , Philippe Flajolet, An introduction to the analysis of algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 48: Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences, John Wiley & Sons, Inc., New York, NY, 2001
• 49: Brigitte Vallée. Dynamics of the binary Euclidean algorithm: Functional analysis and operators. Algorithmica, 22(4):660--685, 1998.
• 50: Brigitte Vallée. Dynamical sources in information theory: Fundamental intervals and word prefixes. Algorithmica, 29(1/2):262--306, 2001.
• 51: Brigitte Vallée. Euclidean dynamics. Discrete and Continuous Dynamical Systems, 15(1):281--352, 2006.
• 52: Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002 [doi>10.1006/jsco.2002.0562]
• 53: Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 54: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 55: Herbert S. Wilf, Generating functionology, Academic Press Professional, Inc., San Diego, CA, 1990
• 56: Doron Zeilberger, A holonomic systems approach to special functions identities, Journal of Computational and Applied Mathematics, v.32 n.3, p.321-368, Nov. 27, 1990 [doi>10.1016/0377-0427(90)90042-X]