This course serves as a graduate introduction to enumerative and algebraic combinatorics, with a focus on effective methods. Our core topics include ordinary and exponential generating functions, classical combinatorics objects (partitions, lattice paths, graphs, permutations), asymptotic methods, sequences satisfying linear recurrence relations, and the occurrence and behaviour of rational, algebraic, and D-finite functions. Depending on student interest, more advanced topics could include multivariate generating functions, computer algebra tools for combinatorics, algorithmic transcendence of constants vs generating functions, computability and complexity questions in enumeration, and connections to formal languages.
Schedule: We meet once a week from 1pm until 4pm each Monday in PK-4323. The first thirty minutes to an hour of each class will be a problem solving session.
Evaluation: 20% participation in the exercise sessions (you don't need to have formal solutions, but you need to participate in our discussion). Every student must present one solution of a problem at the front of the class during the semester (you only need to do this once). When you see a problem whose solution you want to present please email me before the class in which you want to present so that I know you will prepare the problem. The first person to request a problem will get to present it.
80% for a final project: 40% for a summary of a research paper related to the class and 40% for a 20 minute in class presentation about the subject. I will meet with students half way through the semester to discuss project topics (or earlier if desired).
Guidelines for final project: Project Guidelines
(You may need to right click and select "Download / Save as". Also a .xml extension is sometimes added which may need to be removed after downloading)
Maple Worksheet September 9 (Algebraic Numbers and Making Change for a Dollar)
Maple Worksheet - Class September 16
Maple Worksheet - Problem Session September 16
Maple Worksheet - Class October 21
Maple Worksheet - Review Class November 4
Sage Worksheet - Numeric Analytic Continutation, November 18
Sage Worksheet - D-finite Example, November 18
Sage Worksheet - Central Binomial Squared, November 18
Sage Worksheet - NSEW Quadrant Walks, November 18
Problem Sheet 1 (due/to be discussed September 16)
Problem Sheet 2 (due/to be discussed September 23)
Problem Sheet 3 (due/to be discussed September 30)
Problem Sheet 4 (due/to be discussed October 7)
Problem Sheet 5 (due/to be discussed October 28)
Review Problems (we will discuss during lecture Nov 4)
Problem Sheet 6 (due/to be discussed lecture Nov 11)
Problem Sheet 7 (due/to be discussed lecture Nov 18)
Problem Sheet 8 (due/to be discussed lecture Nov 25)
Problem Sheet 9 (due/to be discussed lecture Dec 2)
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.
Here is a sample list of papers that would make good
potential projects (in no particular order). You do not have to pick a paper listed here (about halfway through the semester I will meet with each student to discuss what parts of the course interest them the most, and help them decide on a suitable project topic):
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)
Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behaviour. S. Melczer and M. Wilson. Submitted 2018.
Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems
S. Melczer and B. Salvy. arxiv preprint, 2019.
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.