Compter sans tout écrire : listes, arrangements, combinaisons et triangle de Pascal

Au Loto, on coche 5 numéros parmi 49, puis un « numéro chance » parmi 10. Il existe 19 068 840 grilles : les écrire prendrait des années. Le dénombrement, l'art de compter sans énumérer, se cache derrière chaque probabilité « cas favorables sur cas possibles ».

1. Le principe multiplicatif

Le cardinal card(E) d'un ensemble fini E est son nombre d'éléments. Le produit cartésien A × B est l'ensemble des couples (a ; b) avec a dans A et b dans B, et card(A × B) = card(A) × card(B). Un choix en étapes successives, dont le nombre de possibilités ne dépend pas des choix précédents, se compte en multipliant : 3 entrées, 4 plats et 2 desserts font 24 menus.

Les k-uplets. Un k-uplet d'un ensemble E à n éléments est une liste ordonnée de k éléments de E, répétitions permises : il y en a nᵏ. Un cadenas à 4 molettes de 0 à 9 : 10⁴ = 10 000 codes.

Les parties. Pour former une partie de E, on décide pour chaque élément : dedans ou dehors. C'est un n-uplet de {dedans ; dehors}, donc un ensemble à n éléments a 2ⁿ parties (vide et E compris).

2. Arrangements et permutations

Un arrangement de k éléments de E (k ≤ n) est un k-uplet d'éléments deux à deux distincts : l'ordre compte, sans répétition. Avec n choix pour le premier, n − 1 pour le deuxième…, leur nombre vaut n × (n − 1) × … × (n − k + 1) = n!(n − k)!, où n! = 1 × 2 × … × n (« factorielle n ») et 0! = 1.

Une permutation de E est un arrangement de ses n éléments : il y en a n!. MATHS a 5! = 120 anagrammes ; LYCEE, dont les deux E s'échangent sans changer le mot, en a 5!2! = 60.

3. Combinaisons et coefficients binomiaux

Une combinaison de k éléments de E est une partie de E à k éléments, sans ordre. Leur nombre est le coefficient binomial « k parmi n » : ton manuel l'écrit n au-dessus de k entre parenthèses, on le note ici C(n, k).

Chaque combinaison s'ordonne de k! façons : le nombre d'arrangements vaut C(n, k) × k!, d'où :

C(n, k) = n!k! × (n − k)! = n × (n − 1) × … × (n − k + 1)k!

Exemple 1. Élire 3 délégués sans rôle distinct parmi 25 élèves : C(25, 3) = 25 × 24 × 233 × 2 × 1 = 2 300 groupes. Avec président, trésorier et secrétaire, l'ordre compte : 25 × 24 × 23 = 13 800.

Exemple 2. Au Loto : C(49, 5) = 49 × 48 × 47 × 46 × 45120 = 1 906 884 choix de numéros, et 10 fois plus de grilles avec le numéro chance.

Bon réflexe : l'ordre compte-t-il ? Les répétitions sont-elles possibles ? Les deux : nᵏ. L'ordre seul : arrangements. Ni l'un ni l'autre : C(n, k).

4. Propriétés et triangle de Pascal

• C(n, 0) = C(n, n) = 1 et C(n, 1) = n.
• Symétrie : C(n, k) = C(n, n − k), car choisir les k éléments qu'on garde, c'est choisir les n − k qu'on laisse.
• Relation de Pascal : pour 0 ≤ k ≤ n − 1, C(n, k) + C(n, k + 1) = C(n + 1, k + 1).

Démonstration : ajoutons à E un nouvel élément a. Une partie à k + 1 éléments de E ∪ {a} contient a, ses k autres éléments étant pris dans E (C(n, k) façons), ou ne contient pas a (C(n, k + 1) façons). Ces cas disjoints s'additionnent.

Dans le triangle de Pascal, chaque nombre est donc la somme du nombre juste au-dessus et du voisin de gauche de celui-ci :

n	C(n, 0) … C(n, n)
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1

La somme de la ligne n vaut 2ⁿ : on y compte toutes les parties, selon leur taille. C(n, k) compte aussi les chemins à k succès de la loi binomiale.

À retenir

• Un ensemble à n éléments a nᵏ k-uplets et 2ⁿ parties.
• Arrangements de k éléments parmi n (ordre, sans répétition) : n!(n − k)! ; permutations : n!.
• Combinaisons (parties à k éléments) : C(n, k) = n!k! × (n − k)!.
• C(n, k) = C(n, n − k) et C(n, k) + C(n, k + 1) = C(n + 1, k + 1) : la règle du triangle de Pascal.

★ Pour aller plus loin

Pascal rédige son « Traité du triangle arithmétique » en 1654, mais le triangle est plus ancien : le Persan al-Karaji le décrit vers l'an 1000, le Chinois Yang Hui le publie au XIIIᵉ siècle, et les Italiens l'appellent « triangle de Tartaglia ». Colorie ses cases impaires : une fractale apparaît, le triangle de Sierpiński.

Un jeu de 52 cartes s'ordonne de 52! façons, environ 8 × 10⁶⁷ : ton prochain mélange sera sans doute unique dans l'histoire. Le nom « coefficients binomiaux » vient de la formule du binôme de Newton, qui développe (a + b)ⁿ.

Sources pour creuser

• Livres : Mickaël Launay, « Le Grand Roman des maths » (Flammarion) ; Denis Guedj, « Le Théorème du perroquet » (Seuil).
• Vidéos : chaîne YouTube « Yvan Monka » (cherche « Monka combinaisons », « Monka triangle de Pascal ») ; chaîne « Micmaths ».
• Sites : lumni.fr ; maths-et-tiques.fr ; eduscol.education.fr (programme de Terminale).