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.
- 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]
- 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]
- 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.
- 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.
Relevant links