Stephen Melczer

CRM-ISM Postdoctoral Fellow
PK-4130, Laboratoire de Combinatoire et d’informatique Mathématique (LaCIM)
Université du Québec à Montréal

MATH 7352 (Fall 2019)
Combinatoire I

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


Worksheets

(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


Problem Sheets

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)


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)

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.


Project Ideas


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.
https://lipn.univ-paris13.fr/~banderier/Papers/Alg.pdf

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.
https://www.sciencedirect.com/science/article/pii/S0196885800907115

Philippe Flajolet. Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci., 49(2-3):283–309, 1987.
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ambcfl.pdf

Scott Garrabrant and Igor Pak. Pattern avoidance is not p-recursive. 2015.
https://arxiv.org/abs/1505.06508

Charlotte Hardouin. Galoisian approach to differential transcendence. In Galois theories of linear difference equations: an introduction, volume 211 of Math. Surveys Monogr.
http://www.math.univ-toulouse.fr/~hardouin/notescolombiacharlotte.pdf

Marc Mezzarobba. Rigorous multiple-precision evaluation of D-finite functions in SageMath.
https://arxiv.org/abs/1607.01967
Marc Mezzarobba and BrunoSalvy. Effective bounds for P-recursive sequences. J.Symbolic Comput., 45(10):1075–1096, 2010.
https://arxiv.org/abs/0904.2452

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.
http://www.cs.ox.ac.uk/james.worrell/soda_final.pdf
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.
http://www.cs.ox.ac.uk/james.worrell/ultimate4.pdf


Herbert S. Wilf and Doron Zeilberger. Rational functions certify combinatorial identities. J. Amer. Math. Soc., 3(1):147–158, 1990.
http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/rational.pdf

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.
http://adamczewski.perso.math.cnrs.fr/Diagonals_Final.pdf

Alin Bostan, Louis Dumont, and Bruno Salvy. Algebraic diagonals and walks: algorithms, bounds, complexity. J. Symbolic Comput., 83:68–92, 2017.
https://www.lptmc.jussieu.fr/files/ABDELAZIZ/Dumont2.pdf

Alin Bostan, Pierre Lairez, and Bruno Salvy. Multiple binomial sums. J. Symbolic Comput., 80(part 3):351–386, 2017.
https://arxiv.org/abs/1510.07487

Scott Garrabrant and Igor Pak. Counting with irrational tiles. ArXiv e-prints, 2014.
https://arxiv.org/abs/1407.8222

Maxim Kontsevich and Don Zagier. Periods. In Mathematics unlimited—2001 and beyond, pages 771–808. Springer, Berlin, 2001.
https://www.maths.ed.ac.uk/~v1ranick/papers/kontzagi.pdf

Pierre Lairez. Computing periods of rational integrals. Math. Comp., 85(300):1719–1752, 2016.
https://arxiv.org/abs/1404.5069

Robin Pemantle and Mark C. Wilson. Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev., 50(2):199–272, 2008.
https://arxiv.org/abs/math/0512548

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
http://pracownicy.uksw.edu.pl/mwolf/Poorten_MI_195_0.pdf

Alin Bostan, Mireille Bousquet-Mélou, and Stephen Melczer. Walks with large steps in an orthant. Submitted 2018.
https://arxiv.org/abs/1806.00968

Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. In: Proc. Amer. Math. Soc. 138.9. 2010
https://arxiv.org/abs/0909.1965

Alin Bostan, Kilian Raschel, and Bruno Salvy. “Non-D-finite excursions in the quarter plane”. In: J. Combin. Theory Ser. A 121 (2014)
https://arxiv.org/abs/1205.3300

Stéphane Fischler and Tanguy Rivoal. “On the values of G-functions”. In: Comment. Math. Helv. 89.2 (2014)
https://arxiv.org/abs/1103.6022

Joris van der Hoeven. “Fast evaluation of holonomic functions near and in regular singularities”. In: J. Symbolic Comput. 31.6 (2001)
https://www.sciencedirect.com/science/article/pii/S0747717100904747

Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behaviour.  S. Melczer and M. Wilson. Submitted 2018.
https://arxiv.org/abs/1810.06170

Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems
S. Melczer and B. Salvy. arxiv preprint, 2019.
https://arxiv.org/abs/1905.04187

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.
https://www.math.upenn.edu/~pemantle/papers/bivariate.pdf

Baryshnikov, Y. and Pemantle, R. (2011). Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., vol. 228, pages 3127--3206.
https://www.math.upenn.edu/~pemantle/papers/cones.pdf


Pemantle, R. (2012). Hyperbolicity and stable polynomials in combinatorics and probability. In: Current Development in Mathematics, Proceedings of the 2011 conference, pages 57--124.
https://www.math.upenn.edu/~pemantle/papers/hyperbolic.pdf