Objectifs

Il s'agit d'un cours qui présente quelques objets et outils classiques ou actuels de la combinatoire, avec un fort accent mis sur la combinatoire énumérative et bijective, ses aspects algorithmiques et ses liens avec la physique statistique. NOTE: this page is in French but the course will most likely be in English!

Plan du cours et intervenants prévus pour 2025-2026

Le cours prendra la forme de séances de 2h30 et aura lieu le vendredi de 13h à 15h30 (le cours a lieu au milieu du créneau 12h45-15h45). Les cours auront probablement lieu en anglais, sauf si l'auditoire est francophone. Les supports de cours et sujet d'examen sont en anglais.

Les intervenants seront cette année Guillaume Chapuy (IRIF, Paris) Enrica Duchi (IRIF, Paris), Matthieu Josuat-Vergès (IRIF, Paris), et Gilles Schaeffer (LIX, Palaiseau).

Le cours porte à la fois sur des méthodes fondamentales d'énumération et de génération aléatoire, et sur l'étude plus approfondie de familles d'objets combinatoires particulièrement intéressants (et qui donnent l'occasion de revenir sur et d'utiliser les techniques fondamentales).

Le plan prévisionnel du cours (dates à venir prochainement…):

• Introduction, Inclusion-Exclusion, Théorème BEST, Théorème Matrix-tree, Série génératrices, Arbres, Lemme cyclique, inversion de Lagrange.
• Cartes planaires. Méthodes d'énumération symbolique (méthode du noyau, méthode quadratique) et par décompositions bijectives (tranches, géodésiques).
• Examen 1
• Autres modèles de combinatoire structurelle, parmi: arbres, forêts, ordres partiels, partitions.
• Algorithmes de génération aléatoire et de codage.
• Exam 2

Modalités et annales d'examen

L'évaluation est basée sur deux examens, l'un à la fin de la première période et l'autre à la fin de la deuxième période, tous deux sur table et d'une durée de 2h30. La note finale est la moyenne (arithmétique !) des notes des deux examens.

Ci-dessous quelques annales des années passées (attention le programme des cours, notamment dans la seconde période, peut être assez différent d'une année sur l'autre)
sujet 2011 sujet 1ère période 2012/2013 sujet 2ème période 2012/2013 Sujet et Corrigé, 1ère période 2015/2016 Sujet et Corrigé, 1ère période 2016/2017 sujet 2ème période 2016/2017 sujet 2ème période 2017/2018

Quelques notes de cours qui peuvent être utiles: lecture notes for the first part of the course (covering more subjects, but possibly not covering everything – the only way to know is to attend the lectures!) un chapitre de livre qui recoupe largement le cours et un complément au sujet du jardin de Catalan un chapitre de livre plus détaillé sur l'énumération des cartes notes de cours sur la génération aléatoire.

Pré-requis

Elements d'algèbre élémentaire, principes d'algorithmique.

Cours liées

Le cours est très lié au cours AOFA, bien que chacun des deux puisse être suivi indépendemment de l'autre: COMBIAA et AOFA traitent parfois des mêmes problèmes, d'un point de vue exact et bijectif dans COMBIAA, d'un point de vue asymptotique dans AOFA.

Plus généralement le cours COMBIAA s'inscrit naturellement dans un parcours algorithmique.

Bibliographie

• 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

Équipe pédagogique