Bijections et dénombrement¶
Domaine : Combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
Pour compter un ensemble \(A\), on cherche une bijection entre \(A\) et un ensemble \(B\) facile à compter : chaque élément de \(A\) correspond à exactement un élément de \(B\), et inversement. Alors \(|A| = |B|\).
Pour comparer deux ensembles, une injection de \(A\) dans \(B\) (deux éléments distincts ont des images distinctes) suffit à montrer \(|A| \leq |B|\).
Pour vérifier qu'une application est une bijection, le plus sûr est d'écrire l'application réciproque et de vérifier qu'elle tombe bien dans le bon ensemble.
Les autres outils de base :
- principe additif : on découpe en cas disjoints et l'on additionne ;
- principe multiplicatif : des choix successifs indépendants se multiplient ;
- complémentaire : compter ce qu'on ne veut pas, et le soustraire du total ;
- inclusion-exclusion : \(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\), et de même avec plus d'ensembles.
Dénombrements de base¶
| Objets | Nombre |
|---|---|
| Parties de \(\{1, \ldots, n\}\) | \(2^n\) |
| Parties à \(k\) éléments | \(\binom{n}{k} = \frac{n!}{k!\,(n-k)!}\) |
| Suites de \(k\) éléments distincts parmi \(n\) | \(\frac{n!}{(n-k)!}\) |
| Solutions de \(x_1 + \cdots + x_k = n\) en entiers \(\geq 0\) | \(\binom{n+k-1}{k-1}\) (méthode des étoiles et des barres) |
| Chemins de \((0, 0)\) à \((a, b)\) par pas vers la droite ou vers le haut | \(\binom{a+b}{a}\) |
| Chemins de \((0, 0)\) à \((n, n)\) qui ne passent jamais sous la diagonale | Nombre de Catalan \(\frac{1}{n+1}\binom{2n}{n}\) |
Étoiles et barres. Une solution de \(x_1 + \cdots + x_k = n\) correspond à une rangée de \(n\) étoiles et \(k - 1\) barres : \(x_1\) étoiles, une barre, \(x_2\) étoiles, etc. Il suffit de choisir la place des \(k - 1\) barres parmi \(n + k - 1\) positions.
Exemple résolu¶
Problème
Combien de parties à \(k\) éléments de \(\{1, 2, \ldots, n\}\) ne contiennent pas deux entiers consécutifs ?
Étape 1 : écrire les objets. Une telle partie s'écrit \(a_1 < a_2 < \cdots < a_k\) avec \(a_{i+1} \geq a_i + 2\) pour tout \(i\). La contrainte « pas de voisins » empêche de compter directement.
Étape 2 : resserrer les éléments. On pose \(b_i = a_i - (i - 1)\), c'est-à-dire qu'on décale le \(i\)-ème élément de \(i - 1\) vers la gauche. Alors
Les \(b_i\) forment donc une partie quelconque à \(k\) éléments de \(\{1, \ldots, n - k + 1\}\).
Étape 3 : vérifier la bijection. Réciproquement, si \(b_1 < \cdots < b_k\) sont dans \(\{1, \ldots, n - k + 1\}\), alors \(a_i = b_i + (i - 1)\) vérifie \(a_{i+1} - a_i = b_{i+1} - b_i + 1 \geq 2\) et \(a_k \leq n\). Les deux transformations sont réciproques l'une de l'autre.
Conclusion. Il y a autant de telles parties que de parties à \(k\) éléments de \(\{1, \ldots, n - k + 1\}\), soit \(\binom{n - k + 1}{k}\).
Le réflexe : une contrainte gênante se supprime souvent par une bijection (un décalage, un complémentaire, un codage), qui ramène à un dénombrement connu.
Comment le reconnaître¶
- L'énoncé demande combien il y a d'objets d'un certain type, et la réponse attendue est une formule simple (\(2^{n-1}\), un coefficient binomial, un nombre de Catalan).
- On doit montrer que deux quantités sont égales : chercher une bijection entre les objets qu'elles comptent.
- On doit montrer qu'une quantité est plus petite qu'une autre : chercher une injection.
- Les objets ont une contrainte (pas de voisins, ordre imposé, somme fixée) qu'une transformation pourrait faire disparaître.
Techniques classiques¶
| Situation | Technique |
|---|---|
| Contrainte sur des positions | Décaler pour se ramener à des parties quelconques (exemple résolu) |
| Montrer \(\lvert A \rvert = \lvert B \rvert\) | Bijection explicite, avec sa réciproque |
| Montrer \(\lvert A \rvert \leq \lvert B \rvert\) | Injection de \(A\) dans \(B\) |
| Plusieurs conditions qui se chevauchent | Inclusion-exclusion, ou passage au complémentaire |
| Répartir des objets identiques | Étoiles et barres |
| Chemins interdits sous une droite | Principe de réflexion (nombres de Catalan) |
| Identité entre coefficients binomiaux | Double comptage |
| Objets construits pas à pas | Une relation de récurrence sur leur nombre |
Exercices d'échauffement¶
- Combien l'équation \(x + y + z = 10\) a-t-elle de solutions en entiers positifs ou nuls ?
- Combien y a-t-il de chemins de \((0, 0)\) à \((5, 3)\) par pas d'une unité vers la droite ou vers le haut ?
- Combien d'entiers de \(1\) à \(1000\) ne sont divisibles ni par \(2\), ni par \(3\), ni par \(5\) ?
- Montrer que, pour \(n \geq 1\), \(\{1, \ldots, n\}\) a autant de parties de cardinal pair que de parties de cardinal impair. Indication : ajouter ou retirer l'élément \(1\).
- Une composition de \(n\) est une écriture \(n = c_1 + c_2 + \cdots + c_r\) avec des entiers \(c_i \geq 1\), l'ordre comptant. Montrer qu'il y a \(2^{n-1}\) compositions de \(n\). Indication : couper une rangée de \(n\) points.
Bijections dans la shortlist¶
- 2020 C1, solution 2 : les permutations valables correspondent aux pavages d'une bande \(1 \times n\) par des dominos et des carrés.
- 2019 C3, solution 4 : une bijection entre les configurations et les suites croissantes \(a_1 < \cdots < a_t \leq n\).
- 2022 C5 : une injection de l'ensemble des \(n^n\) fonctions dans l'ensemble des fonctions étudiées donne la minoration.
- 2025 C5 : on répartit les inversions en types et l'on construit des injections entre eux.
- 2017 C3, solution 2 : le nombre d'entiers \(\leq 2^n\) ayant au plus \(k - 1\) chiffres \(1\) en base \(2\) vaut \(\sum_{j < k} \binom{n}{j}\).
Pour approfondir : Objectif Olympiades de Mathématiques, tome 3 (M. Aassila), p. 37 à 45 (équipotence et cardinaux, formule du crible p. 40), p. 46 à 63 (analyse combinatoire, binôme de Newton p. 55, étoiles et barres p. 57 à 59, récapitulatif p. 62), p. 64 à 80 (principes additif et multiplicatif, exemples), p. 84 (nombres de Catalan), p. 133 à 145 (coefficients binomiaux et multinomiaux, Vandermonde p. 138, boules dans des urnes p. 144), p. 211 à 250 (inclusion-exclusion, problème des ménages p. 217) ; tome 4, p. 55 à 112 (fonctions génératrices, partitions d'un entier p. 70).
Pour aller plus loin : bijections sur les partitions d'un entier¶
Une partition de \(n\) est une écriture de \(n\) comme somme d'entiers \(\geq 1\), sans tenir compte de l'ordre. On range les parts par ordre décroissant : par exemple, \(4\) a cinq partitions, \(4\), \(3 + 1\), \(2 + 2\), \(2 + 1 + 1\) et \(1 + 1 + 1 + 1\). Il n'y a pas de formule simple pour leur nombre, mais des bijections montrent que certaines familles de partitions ont la même taille.
Le diagramme de Ferrers et la conjugaison¶
On dessine une partition par des lignes de points, une ligne par part, de la plus longue à la plus courte. Voici \(7 = 4 + 2 + 1\) :
● ● ● ● part 4
● ● part 2
● part 1
En lisant le diagramme par colonnes au lieu de lignes, on obtient une autre partition de \(7\) : les colonnes ont \(3, 2, 1, 1\) points, d'où \(7 = 3 + 2 + 1 + 1\). C'est la partition conjuguée. Conjuguer deux fois redonne la partition de départ, donc la conjugaison est une bijection de l'ensemble des partitions de \(n\) dans lui-même.
Le nombre de lignes devient la longueur de la première colonne, c'est-à-dire la plus grande part. D'où :
Conséquence
Le nombre de partitions de \(n\) en exactement \(k\) parts est égal au nombre de partitions de \(n\) dont la plus grande part vaut exactement \(k\).
Par exemple, \(10\) a \(8\) partitions en \(3\) parts, et \(8\) partitions de plus grande part \(3\).
Parts impaires et parts distinctes (Euler)¶
Théorème (Euler)
Le nombre de partitions de \(n\) en parts impaires est égal au nombre de partitions de \(n\) en parts distinctes.
Pour \(n = 6\), il y en a \(4\) de chaque sorte. Voici la bijection, due à Glaisher.
Des parts impaires vers les parts distinctes. Dans une partition en parts impaires, regroupons les parts égales : la part impaire \(m\) apparaît \(k\) fois. On écrit \(k\) en base \(2\), comme somme de puissances de \(2\) distinctes, \(k = 2^{j_1} + 2^{j_2} + \cdots\), et l'on remplace les \(k\) copies de \(m\) par les parts \(2^{j_1} m, 2^{j_2} m, \ldots\) La somme ne change pas.
Les parts obtenues sont distinctes. Tout entier s'écrit de façon unique \(2^j m\) avec \(m\) impair. Deux parts obtenues égales auraient donc le même \(m\) et le même \(j\) : elles viendraient de la même puissance de \(2\) dans l'écriture binaire du même \(k\), ce qui est impossible.
La réciproque. Dans une partition en parts distinctes, on écrit chaque part \(2^j m\) avec \(m\) impair, et on la remplace par \(2^j\) copies de \(m\). On obtient des parts impaires, et l'on revient exactement à la partition de départ, car l'écriture en base \(2\) est unique.
| Parts impaires | Regroupement | Parts distinctes |
|---|---|---|
| \(5 + 1\) | \(5\) une fois, \(1\) une fois | \(5 + 1\) |
| \(3 + 3\) | \(3\) deux fois, \(2 = 2^1\) | \(6\) |
| \(3 + 1 + 1 + 1\) | \(1\) trois fois, \(3 = 2^0 + 2^1\) | \(3 + 2 + 1\) |
| \(1 + 1 + 1 + 1 + 1 + 1\) | \(1\) six fois, \(6 = 2^1 + 2^2\) | \(4 + 2\) |
Le tome 4 démontre ce théorème avec les fonctions génératrices ; la bijection en donne une preuve sans calcul, qui dit en plus quelle partition correspond à quelle autre.
Exercices.
- Montrer que le nombre de partitions de \(n\) en au plus \(k\) parts est égal au nombre de partitions de \(n\) dont toutes les parts sont \(\leq k\).
- Une partition est auto-conjuguée si elle est égale à sa conjuguée. Montrer que le nombre de partitions auto-conjuguées de \(n\) est égal au nombre de partitions de \(n\) en parts impaires distinctes. Indication : découper le diagramme en équerres emboîtées.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 70 à 78 (partitions d'un entier, théorème d'Euler p. 72).
Problèmes de la shortlist¶
24 problèmes · difficulté moyenne : ★★★★★ (2,8) · dont 5 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 6 · 2 ★ : 5 · 3 ★ : 5 · 4 ★ : 4 · 5 ★ : 4
| Problème | Difficulté | Concepts |
|---|---|---|
| 2024 A2 | ★☆☆☆☆ | Principe extrémal · Récurrence et constructions récursives |
| 2020 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2019 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2016 C1 | ★☆☆☆☆ | - |
| 2013 A1 | ★☆☆☆☆ | Suites et récurrences · Polynômes : racines, relations de Viète, factorisation |
| 2011 C1 · OIM P4 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2019 C3 · OIM P5 | ★★☆☆☆ | Récurrence et constructions récursives · Invariants et monovariants |
| 2017 C3 | ★★☆☆☆ | Récurrence et constructions récursives · Suites et récurrences · Invariants et monovariants |
| 2012 N3 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2010 C1 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2008 C2 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2025 C5 | ★★★☆☆ | - |
| 2022 C5 | ★★★☆☆ | Principe extrémal |
| 2011 C5 | ★★★☆☆ | Invariants et monovariants |
| 2008 C4 · OIM P5 | ★★★☆☆ | Double comptage |
| 2006 C3 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2015 C6 | ★★★★☆ | Principe extrémal |
| 2014 C8 | ★★★★☆ | Jeux et stratégies gagnantes · Invariants et monovariants |
| 2012 C6 · OIM P3 | ★★★★☆ | Jeux et stratégies gagnantes · Invariants et monovariants |
| 2007 C7 | ★★★★☆ | Récurrence et constructions récursives |
| 2022 A8 | ★★★★★ | Suites et récurrences · Principe des tiroirs |
| 2022 C9 | ★★★★★ | Géométrie combinatoire : enveloppe convexe, points du réseau · Partie entière et majorations |
| 2013 C7 · OIM P6 | ★★★★★ | Récurrence et constructions récursives · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2013 N7 | ★★★★★ | Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Partie entière et majorations · Récurrence et constructions récursives |