Dénombrement et combinatoire

Un comité de trois personnes et un podium de trois places ne sont pas le même objet. Dans un comité, échanger deux noms ne crée pas un nouveau comité ; sur un podium, cela change les places. Le premier travail d’un dénombrement est donc de décrire une issue sans ambiguïté. Une formule choisie avant cette description risque de compter plusieurs fois le même objet ou d’en oublier.

Un ensemble fini possède un nombre d’éléments, appelé son cardinal. Un couple est une liste ordonnée de deux éléments, un triplet une liste de trois éléments et un k-uplet une liste de k éléments. Dans un produit cartésien A × B, un couple possède sa première composante dans A et la seconde dans B. Même si A = B, les deux positions restent distinguées.

Le principe additif s’applique quand on partage les objets en catégories disjointes : le cardinal total est la somme des cardinaux. Si les catégories se recouvrent, une addition directe compte plusieurs fois l’intersection. Le principe multiplicatif décrit des choix successifs : si chaque première possibilité donne exactement b secondes possibilités et qu’il y a a premiers choix, le total est ab.

Pour un ensemble de n éléments, le nombre de listes de longueur k avec répétition est nᵏ. À chaque étape, le nombre de possibilités reste n. Si les éléments doivent être distincts et si 0 ≤ k ≤ n, les choix diminuent : n(n − 1)…(n − k + 1). Pour k = n, on obtient toutes les permutations et leur nombre n !, lu factorielle de n.

Par définition, n ! = 1 × 2 × … × n pour n ≥ 1 et 0 ! = 1. La convention 0 ! = 1 est cohérente avec l’existence d’une unique liste vide. Elle permet aussi d’écrire le nombre de listes distinctes sous la forme n !/(n − k) !. Cette écriture n’autorise pas à utiliser une factorielle d’entier négatif quand k > n ; dans ce cas, aucune liste à éléments distincts n’existe.

Chaque partie d’un ensemble de n éléments peut être codée par une liste de n zéros ou uns : pour chaque élément, on inscrit un s’il appartient à la partie et zéro sinon. Les n éléments sont repérés une fois pour toutes afin de fixer les positions. Chaque partie possède un code unique et chaque code décrit une partie unique. Le nombre de parties est donc 2ⁿ.

Cette correspondance relie les parties d’un ensemble, les mots de longueur n sur deux symboles et les chemins d’un arbre à deux choix à chaque étape. En probabilités, les suites de succès et d’échecs dans n épreuves de Bernoulli ont cette même structure de listes. Les dénombrer n’implique pas que tous les chemins aient la même probabilité : cela dépend des paramètres de l’expérience.

Une combinaison de k éléments parmi n est une partie à k éléments. On note son nombre C(n,k), aussi appelé coefficient binomial. Pour 0 ≤ k ≤ n, C(n,k) = n !/[k !(n − k) !]. La présence de k ! au dénominateur vient du changement de point de vue : chaque partie à k éléments peut être ordonnée de k ! façons. On retire donc les multiplicités créées par les positions.

On retrouve C(n,0) = 1, car la partie vide est unique ; C(n,1) = n ; C(n,2) = n(n − 1)/2. De plus, C(n,n) = 1. Pour éviter des calculs inutilement grands, on peut simplifier le produit avant de multiplier ou utiliser une fonction de calcul de coefficient binomial. Il faut néanmoins expliquer pourquoi la situation relève d’une combinaison.

La symétrie C(n,k) = C(n,n − k) s’explique en associant chaque partie à son complémentaire. Choisir k personnes retenues revient à choisir les n − k personnes non retenues. Cette correspondance est réversible ; les deux collections ont donc le même nombre d’éléments. Elle simplifie le calcul de C(20,18), égal à C(20,2) = 190.

La relation de Pascal est C(n,k) + C(n,k + 1) = C(n + 1,k + 1), pour 0 ≤ k ≤ n − 1. Pour la démontrer par dénombrement, on fixe un élément d’un ensemble de n + 1 éléments et on partage ses parties à k + 1 éléments en deux catégories disjointes. Celles qui contiennent l’élément fixé se complètent en choisissant k éléments parmi les n autres ; celles qui ne le contiennent pas se choisissent entièrement parmi les n autres.

Le principe additif donne alors la relation annoncée. Par le calcul, les deux fractions n !/[k !(n − k) !] et n !/[(k + 1) !(n − k − 1) !] ont pour dénominateur commun (k + 1) !(n − k) !. Leurs numérateurs deviennent n !(k + 1) et n !(n − k). Leur somme vaut n !(n + 1) = (n + 1) !, ce qui donne le coefficient de droite.

Pour générer une ligne, on part de [1]. À chaque passage, on place un au début et à la fin, et on calcule les termes intérieurs en additionnant deux voisins de l’ancienne ligne. Il faut conserver cette ancienne ligne pendant le calcul : modifier ses valeurs au fur et à mesure fausserait les suivantes. Cette précaution relie la formule mathématique et la mise au point d’un algorithme.