Principle and objectives

This course introduces some classical and modern objects and tools in combinatorics, with a strong emphasis on enumerative and bijective combinatorics, their algorithmic aspects, and their connections with statistical physics.

Course outline and scheduled speakers for 2026-2027

The course will consist of 2.5-hour sessions and will take place on Friday afternoons. The lectures will most likely be in English, unless the audience is entirely French-speaking. Course material and exams subjects are in English (students can write in English or French).

This year's speakers will be: Guillaume Chapuy (IRIF, Paris) Matthieu Josuat-Vergès (IRIF, Paris), and Gilles Schaeffer (LIX, Palaiseau). The course covers both fundamental methods of enumeration and random generation, as well as a deeper study of particularly interesting families of combinatorial objects (which provide an opportunity to revisit and use fundamental techniques).

• Provisional course outline:
• Introduction, Inclusion-Exclusion, BEST Theorem, Matrix-Tree Theorem, Generating Series, Trees, Cyclic Lemma, Lagrange Inversion.
• Planar Maps. Symbolic enumeration methods (kernel method, quadratic method) and bijective decompositions (slices, geodesics).
• Exam 1
• Other models of structural combinatorics, including: trees, forests, partial orders, partitions.
• Random generation and encoding algorithms.
• Exam 2

Exams

Evaluation is based on two exams, one at the end of the first period and the other at the end of the second period, both in-class and lasting 2.5 hours. The final grade is the (arithmetic) average of the two exam grades. Below are some past exam papers (note: the course content, especially in the second period, may vary significantly from year to year): 2011 exam 2012/2013 first period exam 2012/2013 second period exam 2016/2017 second period exam 2017/2018 second period exam 2022/2023 first period exam with solutions 2024/2025 first period exam with solutions (Note: The subjects covered vary slightly from year to year, so do not worry if you do not recognize some material in past exams.) Some lecture notes that may be useful: Lecture notes for the first part of the course (covering more subjects, but possibly not everything—the only way to know is to attend the lectures!) A book chapter that largely overlaps with the course An additional resource on Catalan's garden A more detailed book chapter on the enumeration of maps Lecture notes on random generation.

Prerequisites

Elements of basic algebra and algorithmic principles.

Related courses

The course is closely related to the AOFA course, although each can be taken independently: COMBIAA and AOFA sometimes address the same problems—from an exact and bijective perspective in COMBIAA, and from an asymptotic perspective in AOFA. More generally, the COMBIAA course fits naturally into an algorithmic curriculum.

Bibliography

Lothaire: Combinatorics on Words,

Knuth: The Art of Computer Programming, Volume 3,

Flajolet, Sedgwick: Analytic Combinatorics,

Stanley: Enumerative Combinatorics,

Wilf: Generatingfunctionology,

Andrews: The Theory of Partitions,

Andrews: q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra

Teaching team