Université du Québec à Montréal

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

(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.

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.

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.

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.

S. Melczer and B. Salvy. arxiv preprint, 2019.

https://arxiv.org/abs/1905.04187

https://www.math.upenn.edu/~pemantle/papers/bivariate.pdf

https://www.math.upenn.edu/~pemantle/papers/hyperbolic.pdf