Examen et corrigé de Combinatoire I - M2 Maths Fondamentales 2019

Présentation de l'examen de Combinatoire I

Ce document rassemble un sujet d'examen de mathématiques accompagné de ses corrigés détaillés, intitulé Combinatoire I, destiné aux étudiants en deuxième année de master (M2) de mathématiques fondamentales. Daté du jeudi 24 octobre 2019, le texte indique clairement les consignes de rédaction et autorise l'usage des notes manuscrites du cours ainsi que des feuilles d'exercices. Les réponses rédigées en anglais sont également acceptées.

Le contenu s'articule autour de cinq exercices indépendants mais complémentaires, explorant des thématiques avancées de combinatoire énumérative, de théorie des graphes et de structures algébriques. Chaque exercice est suivi d'un corrigé rédigé à titre indicatif qui explicite les méthodes de résolution, allant du calcul de séries génératrices à l'utilisation de bijections et de méthodes probabilistes.

Les grands thèmes et exercices abordés

Le premier exercice s'intéresse au pavage de rectangles de dimensions $n \times k$ par des dominos. Les étudiants sont invités à calculer des séries génératrices pour des hauteurs fixes $k = 1$ et $k = 2$ à l'aide de récurrences de type Fibonacci, puis à généraliser la démarche pour $k = 3$ en étudiant les pavages minimaux. Une question démontre également la rationalité de la série génératrice pour tout $k \ge 1$ en modélisant le problème par un parcours sur un graphe dirigé de mots binaires.

L'exercice suivant aborde les cartes planaires et enracinées, plus particulièrement les cartes précubiques caractérisées par des sommets de degré 1 ou 3. Les questions successives permettent d'exprimer le nombre d'arêtes, de faces et de sommets en fonction de l'excès et du nombre de sommets de degré 3, d'analyser la série génératrice des arbres par une décomposition combinatoire, et d'étudier la singularité dominante pour obtenir des équivalents asymptotiques via le théorème de transfert.

Un troisième exercice est consacré aux partitions d'un ensemble à $n$ éléments en $k$ parties disjointes non vides, notées $S_n^{(k)}$. Les questions abordent l'expression à l'aide de constructeurs combinatoires, la relation de récurrence, l'interprétation par des chemins pondérés sur le réseau $\mathbb{Z}^2$, et une application du déterminant avec des n-uplets de chemins non-intersectants, faisant écho au lemme de Gessel-Viennot.

L'exercice quatre traite des arbres et forêts de Cayley sur un ensemble de sommets étiquetés. Il relie le nombre de sommets et d'arêtes, exprime les séries génératrices des arbres avec arêtes ou sommets marqués, et étudie la loi limite du nombre de sommets de degré donné dans une forêt aléatoire de Cayley de grande taille.

Enfin, le dernier exercice aborde les P-partitions sur un ensemble partiellement ordonné, démontrant la rationalité de leur série génératrice et précisant la structure de son dénominateur par une méthode de normalisation.

Modalités d'utilisation pour les révisions

Ce sujet d'examen corrigé constitue un outil de travail direct pour les étudiants préparant des épreuves de combinatoire avancée. Il est recommandé de chercher chaque exercice de manière autonome avant de consulter les corrigés fournis. L'analyse détaillée des méthodes, qu'il s'agisse de l'utilisation de séries génératrices, de décompositions combinatoires ou d'estimations asymptotiques, permet d'assimiler les techniques standard de la discipline.

Questions fréquentes

À quel niveau d'études s'adresse ce document ?

Ce document est destiné aux étudiants en master 2 (M2) de mathématiques fondamentales.

Quels sont les principaux sujets couverts par l'examen ?

L'examen aborde les pavages de rectangles par des dominos, les cartes planaires précubiques, les arbres et forêts de Cayley, les partitions d'ensembles et les P-partitions.

Les corrections sont-elles incluses dans le document ?

Oui, chaque exercice dispose d'un corrigé détaillé fourni à la suite des questions.

Testez vos connaissances

Télécharger Examen et corrigé de Combinatoire I - M2 Maths Fondamentales 2019 pdf