This course provides an introduction to computational and symbolic combinatorics, focused on effective computation and connections to various areas of mathematics. Topics will be tailored to student interests and include: basics of enumerative combinatorics and computer algebra; computer algebra tools for generating functions; effective analytic methods for asymptotics (residue computations, saddle point integrals, etc.); algorithmic transcendence proofs and transcendence of constants vs functions; rational, algebraic, D-finite, differential-algebraic and hypertranscendental functions, and their algebraic/analytic/arithmetic properties; computability and complexity questions in enumeration and connections to formal languages; Morse-theoretic methods for asymptotics; rigorous numerical analytic continuation of functions.
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.). Evaluation will consist of 2 homework assignments during the semester, together with a final presentation on a research paper.
Date and Time: 12:00-1:30pm on Tuesdays and Thursdays in DRL 4C4
Expected Background: Students should be comfortable with the basics of real analysis (especially sequences and series), complex analysis (analytic functions, 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.
The first assignment can be downloaded
Assignment 1 was due Thursday February 21.
The secpnd assignment can be downloaded
Assignment 2 is due Thursday April 4.
Please tell me / meet with me to discuss the topic of your final project by the week of March 18 (either one of the papers below, or another related topic if you have one not on the list in mind). The final project will consist of an ~15 minute presentation to the class about a paper / topic of your choice, and a short 10-15 page summary. The summary should give an overview of the main results and applications, with perhaps a rough idea of how the results are proved. Pretend you are trying to "sell" the paper and get the rest of the students in our class interested in what it's trying to discuss.
Student presentations will take place April 18, 23, 25, and 30 (3 or 4 presentations each day).
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.
Additional details on certain topics can be found in the following sources, all of which are freely available.
P. Flajolet and B. Sedgewick. Cambridge University Press, 2009.
H. Wilf. Academic Press, 1990.
Analytic Combinatorics in Several Variables
R. Pemantle and M. Wilson. Cambridge University Press, 2013.
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.
Additional (not freely available) sources:
Enumerative Combinatorics (volumes 1 and 2)
R. Stanley. Cambridge University Press, 1986 and 1999.
Combinatorial Species and Tree-like Structures
F. Bergeron, G. Labelle, P. Leroux. Cambridge University Press, 1998.
The final project will consist of a summary of a research
paper / papers together with a 15 minute presentation to the
class. The following list contains papers that would make good
potential projects (in no particular order):
Cyril Banderier and Michael Drmota. Formulae and asymptotics for coefficients of algebraic functions. Combin. Probab. Comput., 24(1):1–53, 2015.
E.Barcucci, A.DelLungo, A.Frosini, and S.Rinaldi. A technology for reverse-engineering a combinatorial problem from a rational generating function. Adv. in Appl. Math., 26(2):129– 153, 2001.
Philippe Flajolet. Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci., 49(2-3):283–309, 1987.
Scott Garrabrant and Igor Pak. Pattern avoidance is not p-recursive. 2015.
Charlotte Hardouin. Galoisian approach to differential transcendence. In Galois theories of linear difference equations: an introduction, volume 211 of Math. Surveys Monogr.
Marc Mezzarobba. Rigorous multiple-precision evaluation of D-finite functions in SageMath.
Marc Mezzarobba and BrunoSalvy. Effective bounds for P-recursive sequences. J.Symbolic Comput., 45(10):1075–1096, 2010.
Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 366–379. ACM, New York, 2014.
Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, languages, and programming. Part II, volume 8573 of Lecture Notes in Comput. Sci., pages 330–341. Springer, Heidelberg, 2014.
Herbert S. Wilf and Doron Zeilberger. Rational functions certify combinatorial identities. J. Amer. Math. Soc., 3(1):147–158, 1990.
Boris Adamczewski and Jason P. Bell. Diagonalization and rationalization of algebraic Laurent series. Ann. Sci. Éc. Norm. Supér. (4), 46(6):963–1004, 2013.
Alin Bostan, Louis Dumont, and Bruno Salvy. Algebraic diagonals and walks: algorithms, bounds, complexity. J. Symbolic Comput., 83:68–92, 2017.
Alin Bostan, Pierre Lairez, and Bruno Salvy. Multiple binomial sums. J. Symbolic Comput., 80(part 3):351–386, 2017.
Scott Garrabrant and Igor Pak. Counting with irrational tiles. ArXiv e-prints, 2014.
Maxim Kontsevich and Don Zagier. Periods. In Mathematics unlimited—2001 and beyond, pages 771–808. Springer, Berlin, 2001.
Pierre Lairez. Computing periods of rational integrals. Math. Comp., 85(300):1719–1752, 2016.
Robin Pemantle and Mark C. Wilson. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev., 50(2):199–272, 2008.
Alfred van der Poorten. A proof that Euler missed...Apéry’s proof of the irrationality of ζ(3). Math. Intelligencer, 1(4):195–203, 1978/79
Alin Bostan, Mireille Bousquet-Mélou, and Stephen Melczer. Walks with large steps in an orthant. Submitted 2018.
Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. In: Proc. Amer. Math. Soc. 138.9. 2010
Alin Bostan, Kilian Raschel, and Bruno Salvy. “Non-D-finite excursions in the quarter plane”. In: J. Combin. Theory Ser. A 121 (2014)
Stéphane Fischler and Tanguy Rivoal. “On the values of G-functions”. In: Comment. Math. Helv. 89.2 (2014)
Joris van der Hoeven. “Fast evaluation of holonomic functions near and in regular singularities”. In: J. Symbolic Comput. 31.6 (2001)
E. Rannou. “The complexity of stratification computation”. In: Discrete Comput. Geom. 19.1 (1998)
Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behaviour. S. Melczer and M. Wilson. Submitted 2018.
Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
S. Melczer and B. Salvy. Proceedings of the ACM on ISSAC 201), 333-340, 2016.
(plus forthcoming extension which can be provided)
DeVries, T., van der Hoeven, J. and Pemantle, R. (2011). Automatic asymptotics for coefficients of smooth, bivariate rational functions. Online J. Anal. Comb., vol. 6, 24 pages.
Baryshnikov, Y. and Pemantle, R. (2011). Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., vol. 228, pages 3127--3206.
Pemantle, R. (2012). Hyperbolicity and stable polynomials in combinatorics and probability. In: Current Development in Mathematics, Proceedings of the 2011 conference, pages 57--124.