MATH 581 (Spring 2019)

Combinatorics and Symbolic Computation 

This course provides an introduction to combinatorics, probability theory, and related areas from the perspective of symbolic computation.  Topics include: algorithms for the manipulation of generating functions; effective analytic methods for asymptotics; transcendence proofs; rational, algebraic, rational diagonal, D-finite, and differential-algebraic generating functions and their algebraic/analytic/arithmetic properties; computability questions in enumeration.  Applications from various areas of combinatorics and mathematics will be discussed, tailored to the interests of participants. Familiarity with advanced methods in symbolic computation / computer algebra will not be assumed, however students taking this course for credit will be expected to perform basic coding in a computer algebra system (Maple, Sage, Mathematica, etc.)

Expected Background: Students should be comfortable with the basics of real analysis (sequences and series), complex analysis (Cauchy residue theorem), and algebra (linear algebra, rings and fields). Exposure to courses in computer science, combinatorics,  probability theory, or computer algebra would be beneficial. Interested students unsure of their background should email the instructor for more information.

A good idea of the selection of topics can be found in notes from a recent two week summer school, available here.

Assignments

Will be posted later.

References

The main reference for this class is a manuscript draft which will be distributed, based on the PhD thesis:

Analytic Combinatorics in Several Variables: Effective Asymptotics and Lattice Path Enumeration
S. Melczer. PhD Thesis, University of Waterloo and ENS Lyon, 2017.
https://arxiv.org/abs/1709.05051

Additional details on certain topics can be found in the following sources, all of which are freely available.

Analytic Combinatorics
P. Flajolet and B. Sedgewick. Cambridge University Press, 2009.
http://ac.cs.princeton.edu/home/

Generatingfunctionology
H. Wilf. Academic Press, 1990.
https://www.math.upenn.edu/~wilf/DownldGF.html

Analytic Combinatorics in Several Variables
R. Pemantle and M. Wilson. Cambridge University Press, 2013.
https://www.math.upenn.edu/~pemantle/papers/ACSV.pdf

Algorithmes Efficaces en Calcul Formel [Efficient Algorithms in Computer Algebra]
A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy and E. Schost, 2017.
https://hal.archives-ouvertes.fr/AECF/
(In French)