This is a page of the former Algo team's web site. It won't be updated any longer. # Studies in Automatic Combinatorics

## Combinatorics meets computer algebra!

Here is a series of notes that describe interactions between combinatorial analysis, discrete mathematics, and computer algebra. They discuss combinatorial explorations using the Maple system for symbolic computation, in conjunction with packages like Combstruct, Gfun and Mgfun that are described under the topic Library.

The documents are mostly in the form of Maple Worksheets (mws), Postscript (ps) and Html (html) files.

These pages are maintained by Frédéric Chyzak, Philippe Flajolet, and Bruno Salvy.

# Volume III (2001–2003)

• Special Functions Manipulations
• Borel Resummation of Divergent Series Using Gfun [Frédéric Chyzak, Marianne Durand, and Bruno Salvy]. For some ``irregular singular'' problems coming from differential equations, there exist formal power series solutions that are everywhere divergent. These power series turn out to make sense as asymptotic expansions of actual solutions. The Borel summation technique is used to recover convergent representations for these actual functions solutions. For a fairly large class of integrands, this technique leads to algorithmic calculations using Gfun. [mws | ps | html]
(This session is based on a talk by Lutz at our seminar, of which a summary is also available [ps | pdf].)
• An Algolib-aided version of Apéry's proof of the irrationality of zeta(3) [Bruno Salvy]. This worksheet gives a complete proof of this irrationality. A central part of it has already been discussed in our Volume II (Variations on the Sequence of Apéry Numbers). [mws|ps|html]
• A Computer-Aided Proof of a Corrected Version of 10.2.32 in Abramowitz & Stegun's HMS [Frédéric Chyzak]. This work derives a closed-form for the derivative of the modified Bessel function of the first kind, Iν(x) with regard to the parameter ν, evaluated at ν=1/2, in terms of exponential integrals. The original formula in the celebrated Handbook of Mathematical Functions has a sign error. Here, we rediscover the correct expression. [mw | ps | pdf]

# Volume II (1997)

• Combinatorics
• Combinatorics of Non-Crossing Configurations [Frédéric Cazals]. Take points on a circle and consider graphs based on these points such that no edges cross. A fairly complete theory of these constrained random graphs can be developed. Planarity entails a very strong combinatorial decomposability that is especially well suited to a detailed treatment by Combstruct. [mws (138kb) | ps (407kb) | html]
• Constrained Permutations and the Principle of Inclusion-Exclusion [Philippe Flajolet]. This is a Maple worksheet (Maple, version 5.4) based on the Combstruct and Gfun packages. It shows how to enumerate many classes of permutations with constraints on "succession gaps" (differences between consecutive elements). This covers many celebrated combinatorial problems (like "rencontre" or "menage"). Generating functions, recurrences, and asymptotics can be obtained automatically. [mws (92kb) | ps.gz (105kb) | ps (914kb) | html]
• Robustness in Random Interconnection Graphs [Philippe Flajolet]. This is a Maple worksheet (Maple, version 5.4) based on the Combstruct and Gfun packages. It shows how to characterize the trade-offs between the density of edges in a graph, its connectivity by short paths, and its robustness to link failure. [mws (90kb) | ps.gz (88kb) | ps (721kb) | html]
• Monomer-Dimer Tilings [Frédéric Cazals]. The number of ways a square lattice can be tiled with unit squares and dominoes is a combinatorial problem related to physical models of phase transition. This worksheet applies combstruct to finding bounds on the asymptotic behaviour of this number. [mws | ps | html]
• Special Functions and Combinatorial Identities
• Gfun and the AGM [Bruno Salvy]. The arithmetic-geometric mean is related to hypergeometric functions. This relation and a generalization of it are explored and proved using gfun. [mws | ps | html]
• Variations on the Sequence of Apéry Numbers [Frédéric Chyzak]. Finding a second order recurrence satisfied by combinatorial numbers was a crucial step in Apéry's proof of the irrationality of zeta of 3. In this session, we exemplify an algorithmic method for symbolic summation by rediscovering the recurrence on these numbers and proving a combinatorial identity that they satisfy. We also derive an efficient calculation of the first hundreds of digits of zeta of 3. [mws | ps | html]
• An Integral of a Product of four Bessel Functions [Frédéric Chyzak]. We illustrate an algorithmic method for symbolic integration by computing a closed form for a nice integral involving four types of Bessel functions. [mws | ps | html]
• Asymptotics
• Asymptotics of the Stirling Numbers of the Second Kind [Bruno Salvy]. The asymptotics of the Bell numbers is a classical problem which is traditionally treated by the saddle-point method. The asymptotic scale required to perform the computation is non-trivial, and variants of this problem such as the asymptotic behaviour of the average value or the variance of the Stirling numbers involve an indefinite cancellation in this scale. This worksheet exemplifies the use of a recent algorithm on this problem. [mws | ps | html]

# Volume I (1996)

• Combinatorics
• Enumeration of Planar Configurations in Combinatorial Geometry available as [mws|ps|html]. There, starting with Euler's counting of triangulations of an n-gon, many planar configurations can be counted, listed and randomly generated, automatically. This sheet may serve as an entry point to the Combstruct and Gfun packages.
• Enumerating alcohols and other classes of chemical moleculs, an example of Polya's theory available as [mws|ps|html]. Classes of chemical compounds can be represented by combinatorial models using the Combstruct package.
• Balls and Urns, Etc. available as [mws|ps|html]. Balls and urns models are basic in combinatorics, statistics, analysis of algorithms and statistical physics. We demonstrate here how their properties can be explored using most of the functionalities of the Combstruct package.

• Asymptotics
• Patterns in words available as [mws|ps|html]. How likely is it that a specific pattern occurs k times in a random word of length n? How does the probability of this event depend on the specific pattern? This worksheet applies Combstruct and Gfun to this problem which has a connection to questions from biology of the DNA.
• A Seating Arrangement Problem available as [mws|ps|html]. What happens when n persons arrive at a luncheonette and are so unfriendly that no one wants to sit next to an already occupied seat? This worksheet explores properties of this problem when people arrive randomly. (This also serves as a simplified model of channel occupation in mobile communication.) The complete treatment is entirely based on the Gfun package and Maple's capabilities in solving differential equations.
• Polygons, a simplified model for self-avoiding walks available as [mws|ps|html]. There, we count pairs of non-crossing paths in integer lattices of dimensions 2, 3 and more. We also get numerical asymptotics by a connection method. This sheet makes intensive use of the Gfun package.

• Analytic Combinatorics
• A Problem in Statistical Classification Theory available as [mws|ps|html]. Classification theory makes use of classification trees. This worksheet explores properties of random classification trees using the Combstruct package and Maple.
• Pollard's Rho Algorithm available as [mws|ps|html]. An efficient and simple technique used to find factors of integers. We show in this worksheet how Combstruct and Gfun can be used to analyze a realistic combinatorial model of the algorithm and thus derive a probabilistic complexity analysis of this algorithm and variants of it.

# Introductory worksheets

• Tutorials and Introductions
• Introduction to the Combinatorial Structures Package [Eithne Murray]. This is a light introduction to Combstruct originally written by Eithne Murray; a Maple worksheet version of this file is in the tar file with the code and libraries. There, you'll learn about the basics of specifications, how to get counting sequences, and how to use predefined structures (subsets, permutations, combinations, etc). Worksheet version of this file is in the tar file with the code and libraries. [ps|ms|mws|html]
• Combinatorial Structures Package [Eithne Murray]. Here's a simple collection of Combstruct examples showing how to generate random trees, investigate the distribution of height by simulation, enumerate functional graphs, alcohols (!), necklaces, expression trees, and so on. A Maple worksheet version of this file is in the tar file with the code and libraries. [ps|ms|mws|html]
• The Combstruct Package: New Features [Eithne Murray]. Starting with version 3.0 of Combstruct, it becomes possible to produce generating function equations and to solve some of them. Also, a new function, called allstructs for the exhaustive generation of structures has been added. [ps|mws|html]
• General Functionality
• Analysis of Algorithms with Combstruct [Eithne Murray] Starting with version 3.2 of Combstruct, it is possible to perform some simple complexity analyses of algorithms operating on combstruct structures in the spirit of luo. [ps|mws|html]
• Generating Marked Combstruct Grammars [Marni Mishna]. Version 3.2 contains new functions producing grammars with marked objects. This makes it possible to analyse means and variance of parameters of various combinatorial objects. The basic mechanisms are described here together with examples like: cycles in permutations, path length or leaves in binary trees, and so on. [ps|mws]
• More Examples of Marking Combstruct Grammars [Marni Mishna]. This worksheet continues to explore the possibilities of combstruct[mark]. How far is the common ancestor of two nodes in a random binary tree? What is the average distance between two nodes? This and a few other examples related to non-crossing configurations are to be found there. [ps|mws|html] examples are available

## Contributed pages

We welcome contributed pages. We encourage authors to submit Maple worksheets using Combstruct, Gfun and/or Mgfun.