04 · Combinatoire¶
Intuition
La combinatoire, c'est compter sans énumérer. La difficulté n'est presque jamais la formule — elles tiennent en cinq lignes. Elle est dans le choix du modèle : est-ce que l'ordre compte ? est-ce qu'on peut répéter ?
Ces deux questions, posées dans cet ordre, résolvent 90 % des exercices. Le reste du travail consiste à décomposer un problème compliqué en étapes simples et à multiplier.
C'est aussi le chapitre charnière du semestre : dès qu'un univers probabiliste est fini et équiprobable, calculer une probabilité est un dénombrement.
1. Les deux principes fondamentaux¶
1.1 Principe multiplicatif¶
Principe multiplicatif
Si une construction se fait en \(k\) étapes successives, avec \(n_1\) choix à la première étape, \(n_2\) à la deuxième (quel que soit le choix précédent), …, \(n_k\) à la dernière, alors le nombre total de constructions est
C'est le cardinal d'un produit cartésien : \(\operatorname{Card}(A\times B) = \operatorname{Card}(A)\times\operatorname{Card}(B)\).
Exemple. Une plaque d'immatriculation française est de la forme
AA-123-AA : 2 lettres, 3 chiffres, 2 lettres.
La condition « quel que soit le choix précédent »
Le nombre de choix à l'étape \(i\) doit être le même quelles que soient les décisions antérieures. Il peut en dépendre en nature — mais pas en nombre.
Exemple valide : tirer 3 cartes successivement sans remise dans un jeu de 52. Les cartes disponibles changent, mais leur nombre est toujours 52, 51, 50. Le principe s'applique.
1.2 Principe additif¶
Si un ensemble se décompose en parties deux à deux disjointes, son cardinal est la somme des cardinaux.
La règle de traduction
- « et », étapes successives → on multiplie
- « ou », cas disjoints → on additionne
Si les cas ne sont pas disjoints, il faut le crible (inclusion-exclusion, §6).
2. Les quatre situations de base¶
Tout dénombrement élémentaire consiste à tirer \(k\) objets parmi \(n\). Deux questions, donc quatre cases.
| Ordre compte | Ordre ne compte pas | |
|---|---|---|
| Avec répétition | \(n^k\) | \(\dbinom{n+k-1}{k}\) (hors programme) |
| Sans répétition | \(A_n^k = \dfrac{n!}{(n-k)!}\) | \(\dbinom nk = \dfrac{n!}{k!\,(n-k)!}\) |
Le réflexe à installer
Devant un énoncé, posez toujours les deux questions dans cet ordre :
- Peut-on répéter un objet ?
- Deux tirages qui diffèrent seulement par l'ordre sont-ils comptés une ou deux fois ?
Ensuite seulement, choisissez la formule.
3. Permutations¶
Une permutation de \(n\) objets est un rangement de ces \(n\) objets dans un ordre. Il y en a
Justification par le principe multiplicatif : \(n\) choix pour la première place, \(n-1\) pour la deuxième (un objet est déjà placé), …, 1 pour la dernière.
Convention : \(0! = 1\) — il y a exactement une façon de ne rien ranger, la manière vide.
Ordres de grandeur — utiles pour juger la faisabilité d'une énumération :
| \(n\) | \(n!\) |
|---|---|
| 5 | 120 |
| 10 | 3 628 800 |
| 13 | \(\approx 6{,}2\times10^9\) |
| 20 | \(\approx 2{,}4\times10^{18}\) |
| 70 | \(> 10^{100}\) |
Pourquoi l'énumération brutale est presque toujours impossible
Un problème du voyageur de commerce à 20 villes possède \(19!/2 \approx 6\times10^{16}\) tours distincts. À un milliard de tours évalués par seconde, cela demande deux ans. À 25 villes, plus de 500 000 ans.
C'est l'argument qui justifie l'existence même de la recherche opérationnelle et des méthodes de séparation-évaluation enseignées en deuxième année.
4. Arrangements¶
Un arrangement de \(k\) éléments parmi \(n\) est un tirage ordonné, sans répétition.
Il y a exactement \(k\) facteurs dans le produit développé.
Cas particulier : \(A_n^n = n!\) — un arrangement de tous les éléments est une permutation.
Exemple. Un podium (or, argent, bronze) parmi 8 athlètes :
L'ordre compte — être premier n'est pas être troisième — et un athlète ne peut occuper deux places.
5. Combinaisons¶
Une combinaison de \(k\) éléments parmi \(n\) est un tirage non ordonné, sans répétition : c'est simplement une partie à \(k\) éléments.
Lu « \(k\) parmi \(n\) ». L'ancienne notation \(C_n^k\) désigne la même chose.
D'où vient la division par \(k!\)
Chaque partie à \(k\) éléments peut être ordonnée de \(k!\) façons différentes, et ces \(k!\) arrangements correspondent à la même combinaison. On a donc compté chaque combinaison exactement \(k!\) fois de trop.
Cette technique — compter avec ordre, puis diviser par le surcomptage — est le mécanisme central de la combinatoire.
Exemple. Une main de 5 cartes dans un jeu de 32 :
5.1 Propriétés¶
La symétrie \(\binom nk = \binom{n}{n-k}\) a une lecture immédiate : choisir \(k\) éléments à prendre, c'est choisir \(n-k\) éléments à laisser. Les deux opérations sont en bijection.
Relation de Pascal
Démonstration combinatoire (sans calcul)
Fixons un élément particulier \(a\) parmi les \(n\). Les parties à \(k\) éléments se répartissent en deux familles disjointes :
- celles qui contiennent \(a\) : il reste à choisir \(k-1\) éléments parmi les \(n-1\) autres, soit \(\binom{n-1}{k-1}\) ;
- celles qui ne le contiennent pas : il faut choisir les \(k\) éléments parmi les \(n-1\) autres, soit \(\binom{n-1}{k}\).
Par le principe additif, le total est la somme. \(\blacksquare\)
Ce type de raisonnement — partitionner selon un cas particulier — est beaucoup plus éclairant qu'un calcul de factorielles, et beaucoup plus rapide.
5.2 Triangle de Pascal¶
Chaque coefficient est la somme des deux au-dessus de lui.
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
Deux lectures immédiates :
- la somme d'une ligne vaut \(2^n\) — c'est le nombre total de parties ;
- la ligne \(n\) donne les coefficients de \((a+b)^n\).
5.3 Formule du binôme de Newton¶
Pourquoi. Développer \((a+b)^n = (a+b)(a+b)\cdots(a+b)\) revient à choisir, dans chacun des \(n\) facteurs, soit \(a\) soit \(b\). Un terme \(a^{n-k}b^k\) apparaît autant de fois qu'il y a de façons de choisir les \(k\) facteurs qui fournissent \(b\) — c'est-à-dire \(\binom nk\).
Conséquences immédiates, obtenues en spécialisant :
La seconde dit qu'il y a autant de parties de cardinal pair que de cardinal impair dans un ensemble non vide.
6. Le crible (inclusion-exclusion)¶
Quand les cas ne sont pas disjoints, on corrige les doubles comptages :
Pour \(n\) ensembles, les signes alternent : on ajoute les cardinaux simples, on retranche les intersections deux à deux, on ajoute celles à trois, etc.
Le complémentaire, souvent plus rapide
Compter « au moins un » est presque toujours plus long que compter « aucun » et soustraire :
C'est le premier réflexe à avoir devant un énoncé contenant « au moins ».
7. Méthode générale de résolution¶
- Identifier l'ensemble à compter. Écrivez-le : « je compte les… ».
- Répétition possible ?
- L'ordre compte-t-il ?
- Décomposer en étapes (multiplicatif) ou en cas disjoints (additif).
- Vérifier sur un petit cas en énumérant à la main.
L'étape 5 n'est pas facultative
Testez toujours votre formule sur \(n=2\) ou \(n=3\), où l'énumération complète est faisable. C'est la seule façon de détecter un surcomptage, et elle prend trente secondes.
Exemples traités¶
Exemple 1 — Les quatre cases sur un même énoncé
On dispose de 5 livres distincts et de 3 étagères.
a) Combien de façons de choisir 3 livres et de les ranger dans l'ordre sur une étagère ? Ordonné, sans répétition : \(A_5^3 = 5\times4\times3 = 60\).
b) Combien de façons de choisir 3 livres à emporter, sans ordre ? \(\binom53 = 10\).
c) Combien de façons d'attribuer une étagère à chacun des 5 livres ? Pour chaque livre, 3 choix indépendants : \(3^5 = 243\).
d) Combien de rangements de tous les 5 livres sur une seule étagère ? \(5! = 120\).
Exemple 2 — Comptage par complémentaire
Un code PIN a 4 chiffres. Combien en contiennent au moins un 7 ?
Total : \(10^4 = 10\,000\).
Aucun 7 : 9 choix par position, soit \(9^4 = 6561\).
Au moins un 7 : \(10\,000 - 6561 = 3439\).
Pourquoi ne pas compter directement
On serait tenté d'écrire « 4 positions pour le 7, \(\times\ 10^3\) pour le
reste \(= 4000\) ». C'est faux : le code 7712 serait compté deux fois
(une fois pour chaque 7). Le comptage direct exige un crible complet ;
le complémentaire fait le travail en une ligne.
Exemple 3 — Anagrammes avec répétitions
Combien d'anagrammes du mot MATHS ? Et du mot ANNEE ?
MATHS : 5 lettres toutes distinctes, donc \(5! = 120\).
ANNEE : 5 lettres, mais avec deux N et deux E. Si on les traitait comme distincts, on aurait \(5! = 120\) mots — mais chaque mot réel serait compté \(2!\times2! = 4\) fois (échanger les deux N, échanger les deux E, ne change rien de visible).
Formule générale : pour un mot de \(n\) lettres où la lettre \(i\) apparaît \(n_i\) fois,
Exemple 4 — Décomposition en étapes
Un comité de 4 personnes est formé parmi 7 femmes et 5 hommes. Combien de comités comportent exactement 2 femmes ?
Deux étapes indépendantes :
- choisir 2 femmes parmi 7 : \(\binom72 = 21\) ;
- choisir 2 hommes parmi 5 : \(\binom52 = 10\).
Total : \(21\times10 = 210\).
Variante — au moins 2 femmes. On additionne les cas disjoints :
Vérification : le total de comités est \(\binom{12}{4} = 495\). Les cas restants sont 0 femme (\(\binom50\binom74\)… non : \(\binom70\binom54 = 5\)) et 1 femme (\(\binom71\binom53 = 70\)). Or \(420+70+5 = 495\) ✓
Erreurs fréquentes¶
| Erreur | Symptôme | Correction |
|---|---|---|
| Utiliser \(A_n^k\) au lieu de \(\binom nk\) | Résultat \(k!\) fois trop grand | L'ordre compte-t-il ? |
| Compter directement « au moins un » | Doubles comptages | Passer au complémentaire |
| Additionner des cas non disjoints | Surcomptage | Crible, ou redécouper |
| Oublier de diviser par les répétitions | Anagrammes surcomptés | Diviser par \(\prod n_i!\) |
| \(\binom nk\) avec \(k>n\) | — | Vaut 0 : on ne choisit pas plus qu'il n'y a |
Exercices¶
★ Exercice 1. Calculer.
a) \(5!\) b) \(A_7^3\) c) \(\binom{6}{2}\) d) \(\binom{10}{7}\)
★ Exercice 2. Un restaurant propose 4 entrées, 6 plats, 3 desserts.
a) Combien de menus complets (entrée + plat + dessert) ? b) Combien de menus si l'entrée est facultative ?
★ Exercice 3. Dans une classe de 25 élèves, on élit un délégué et un suppléant (postes distincts, une même personne ne peut cumuler).
a) Combien de possibilités ? b) Et si l'on choisit simplement 2 représentants sans distinguer les rôles ?
★★ Exercice 4. Un mot de passe fait 8 caractères choisis parmi 26 minuscules, 26 majuscules et 10 chiffres.
a) Combien de mots de passe possibles ? b) Combien contiennent au moins un chiffre ? c) Combien contiennent au moins une majuscule et au moins un chiffre ?
★★ Exercice 5. Combien d'anagrammes des mots suivants ?
a) LOGIQUE b) MATRICE c) STATISTIQUE
★★ Exercice 6. On tire 5 cartes dans un jeu de 52. Combien de mains contiennent :
a) exactement 2 as ? b) au moins 1 as ? c) exactement 3 cœurs et 2 piques ?
★★★ Exercice 7. Démontrer par le calcul, puis par un argument combinatoire :
a) \(\displaystyle k\binom nk = n\binom{n-1}{k-1}\) b) \(\displaystyle\sum_{k=0}^{n}\binom nk = 2^n\) c) \(\displaystyle\sum_{k=0}^{n}k\binom nk = n\,2^{n-1}\)
Pour c), utilisez a) puis b).
★★★ Exercice 8. Combien de chemins mènent du point \((0,0)\) au point \((m,n)\) d'une grille, si l'on ne peut se déplacer que d'un pas vers la droite ou d'un pas vers le haut ?
En déduire une interprétation de la relation de Pascal en termes de chemins.
★★★ Exercice 9. Une urne contient 10 boules numérotées de 1 à 10. On en tire 3 simultanément.
a) Combien de tirages possibles ? b) Combien contiennent uniquement des numéros pairs ? c) Combien contiennent au moins deux numéros consécutifs ?
Indication pour c) : comptez d'abord les tirages sans numéros consécutifs.
★★★★ Exercice 10. Démontrer l'identité de Vandermonde :
Indication : comptez de deux façons les parties à \(k\) éléments d'un ensemble formé de \(m\) boules rouges et \(n\) boules bleues.
En déduire la valeur de \(\displaystyle\sum_{k=0}^{n}\binom nk^2\).
★★★★ Exercice 11 — lien informatique. Un algorithme de force brute teste toutes les clés d'un espace de recherche.
a) Une clé WEP fait 40 bits. Combien de clés ? À \(10^9\) tests par seconde, combien de temps pour toutes les essayer ? b) Une clé AES-128 fait 128 bits. Même question. Comparer à l'âge de l'univers (\(\approx 4{,}4\times10^{17}\) s). c) Un mot de passe de 8 caractères alphanumériques (62 symboles). Combien de bits d'entropie cela représente-t-il, c'est-à-dire quel est le \(n\) tel que \(62^8 \approx 2^n\) ? d) Combien de caractères faudrait-il pour atteindre l'entropie d'AES-128 ?
Corrigés¶
Corrigé — Exercice 1
a) \(5! = 120\).
b) \(A_7^3 = 7\times6\times5 = 210\).
c) \(\binom62 = \dfrac{6\times5}{2} = 15\).
d) \(\binom{10}{7} = \binom{10}{3} = \dfrac{10\times9\times8}{6} = 120\).
(On a utilisé la symétrie pour éviter de calculer avec 7 facteurs.)
Corrigé — Exercice 2
a) \(4\times6\times3 = 72\) menus.
b) L'entrée devient un choix parmi 5 possibilités (4 entrées, ou aucune) : \(5\times6\times3 = 90\).
Autre méthode, par cas disjoints : \(72\) (avec entrée) \(+\ 6\times3 = 18\) (sans) \(= 90\) ✓
Corrigé — Exercice 3
a) Ordonné, sans répétition : \(A_{25}^2 = 25\times24 = 600\).
b) Non ordonné : \(\binom{25}{2} = \dfrac{600}{2} = 300\).
Le rapport est bien \(2! = 2\).
Corrigé — Exercice 4
Alphabet total : \(26+26+10 = 62\) caractères.
a) \(62^8 = 218\,340\,105\,584\,896 \approx 2{,}18\times10^{14}\).
b) Complémentaire : sans chiffre, \(52^8 = 53\,459\,728\,531\,456\).
c) Crible. Notons \(\overline{C}\) l'ensemble des mots sans chiffre et \(\overline{M}\) celui sans majuscule.
(\(36 = 26+10\) pour « sans majuscule », \(26\) pour « ni chiffre ni majuscule »).
Donc au moins une majuscule et au moins un chiffre :
La méthode
« Au moins A et au moins B » se traite en niant : le complémentaire est « pas de A ou pas de B », et c'est là qu'intervient le crible.
Corrigé — Exercice 5
a) LOGIQUE : 7 lettres, dont deux E? Non — L, O, G, I, Q, U, E : toutes
distinctes. \(7! = 5040\).
b) MATRICE : M, A, T, R, I, C, E — 7 lettres distinctes. \(7! = 5040\).
c) STATISTIQUE : 11 lettres. Comptons : S(2), T(3), A(1), I(2), Q(1), U(1), E(1). Total \(2+3+1+2+1+1+1 = 11\) ✓
Corrigé — Exercice 6
a) Choisir 2 as parmi 4, et 3 non-as parmi 48 :
b) Complémentaire — aucune as : \(\binom{48}{5} = 1\,712\,304\). Total : \(\binom{52}{5} = 2\,598\,960\).
c) \(\binom{13}{3}\binom{13}{2} = 286\times78 = 22\,308\).
Corrigé — Exercice 7
a) Par le calcul.
Les deux sont égaux ✓
Argument combinatoire. On compte les couples (comité de \(k\) personnes parmi \(n\), président choisi dans ce comité) :
- à gauche : on forme d'abord le comité (\(\binom nk\)), puis on désigne le président parmi ses \(k\) membres ;
- à droite : on désigne d'abord le président parmi les \(n\) personnes (\(n\) choix), puis on complète le comité avec \(k-1\) membres parmi les \(n-1\) restants.
Les deux comptages portent sur le même ensemble. \(\blacksquare\)
b) Par le binôme avec \(a=b=1\) : \((1+1)^n = \sum\binom nk = 2^n\).
Argument combinatoire. Le membre de gauche compte les parties de \(E\) en les classant par cardinal ; le membre de droite les compte élément par élément (dedans ou dehors). C'est le théorème \(\operatorname{Card}(\mathcal{P}(E)) = 2^n\) du chapitre 02.
c) En utilisant a) :
(changement d'indice \(j = k-1\), puis b) au rang \(n-1\).) \(\blacksquare\)
Interprétation. C'est le nombre total de couples (partie, élément désigné dans cette partie). Autrement dit : la taille moyenne d'une partie tirée au hasard est \(\frac{n2^{n-1}}{2^n} = \frac n2\) — ce qui est intuitivement satisfaisant.
Corrigé — Exercice 8
Un chemin de \((0,0)\) à \((m,n)\) comporte nécessairement \(m\) pas vers la droite
(D) et \(n\) pas vers le haut (H), soit \(m+n\) pas au total. Un chemin est
entièrement déterminé par l'ordre de ces pas, c'est-à-dire par le choix
des positions des H parmi les \(m+n\) pas.
Interprétation de Pascal. Le dernier pas menant à \((m,n)\) vient soit de \((m-1,n)\) (pas vers la droite), soit de \((m,n-1)\) (pas vers le haut). Ces deux familles de chemins sont disjointes et recouvrent tout. Donc
ce qui est exactement la relation de Pascal. \(\blacksquare\)
Le triangle de Pascal est la table du nombre de chemins dans une grille.
Corrigé — Exercice 9
a) Tirage simultané = non ordonné, sans répétition : \(\binom{10}{3} = 120\).
b) Les pairs sont \(\{2,4,6,8,10\}\), au nombre de 5 : \(\binom53 = 10\).
c) Comptons d'abord les tirages sans deux numéros consécutifs.
Soit \(\{a<b<c\}\) un tel tirage : les conditions sont \(b\geqslant a+2\) et \(c\geqslant b+2\). Posons
Alors \(a'<b'<c'\), avec \(1\leqslant a'\) et \(c'\leqslant 8\). Cette transformation est une bijection entre les tirages sans consécutifs dans \([\![1;10]\!]\) et les tirages quelconques dans \([\![1;8]\!]\).
Il y en a donc \(\binom83 = 56\).
Au moins deux consécutifs : \(120 - 56 = 64\).
La technique du décalage
Transformer une contrainte d'écart en une bijection vers un problème sans contrainte est un procédé standard. La formule générale : le nombre de parties à \(k\) éléments de \([\![1;n]\!]\) sans deux éléments consécutifs vaut \(\binom{n-k+1}{k}\). Ici \(\binom{10-3+1}{3} = \binom83 = 56\) ✓
Corrigé — Exercice 10
Double comptage. Soit un ensemble de \(m\) boules rouges et \(n\) boules bleues, toutes distinctes, soit \(m+n\) boules au total. Comptons les parties à \(k\) éléments.
Première façon : directement, \(\binom{m+n}{k}\).
Deuxième façon : on classe selon le nombre \(j\) de boules rouges choisies, \(j\) allant de 0 à \(k\). Pour un \(j\) fixé, il y a \(\binom mj\) façons de choisir les rouges et \(\binom{n}{k-j}\) de choisir les bleues. Les cas sont disjoints (le nombre de rouges est déterminé), donc on additionne :
Les deux comptages portent sur le même ensemble, donc coïncident. \(\blacksquare\)
Application. Prenons \(m = n = k\) :
en utilisant la symétrie \(\binom{n}{n-j} = \binom nj\).
Donc
Vérification \(n=3\) : \(1+9+9+1 = 20\), et \(\binom63 = 20\) ✓
Corrigé — Exercice 11
a) \(2^{40} \approx 1{,}0995\times10^{12}\) clés. À \(10^9\) tests/s : \(\approx 1100\) secondes, soit environ 18 minutes.
C'est la raison pour laquelle WEP a été abandonné — et encore, les attaques réelles sur WEP exploitent des faiblesses du protocole et sont bien plus rapides qu'une force brute.
b) \(2^{128} \approx 3{,}40\times10^{38}\) clés. À \(10^9\) tests/s : \(3{,}40\times10^{29}\) secondes.
Rapport à l'âge de l'univers :
Il faudrait environ 770 milliards de fois l'âge de l'univers. Même en parallélisant sur un milliard de machines, on resterait à 770 fois l'âge de l'univers.
c) \(62^8 \approx 2{,}18\times10^{14}\). On cherche \(n\) tel que \(2^n = 62^8\) :
Un mot de passe alphanumérique de 8 caractères vaut donc environ 48 bits d'entropie — nettement moins que les 128 bits d'AES, et à portée d'une attaque par force brute distribuée.
d) On veut \(62^c \geqslant 2^{128}\), soit
Il faudrait 22 caractères alphanumériques aléatoires pour égaler AES-128.
La limite du calcul
Ce raisonnement suppose les caractères tirés uniformément au hasard. Un mot de passe choisi par un humain a une entropie très inférieure — typiquement 20 à 30 bits pour 10 caractères — parce que la distribution n'est pas uniforme. Le dénombrement donne une borne supérieure, pas la sécurité réelle. C'est exactement le genre de critique de modèle que demande le module de modélisation.
Chapitre suivant : Matrices : opérations de base.