Combinaisons sans répétition

Les combinaisons sans répétition répondent à une question de dénombrement fondamentale en statistique et en mathématiques discrètes : étant donné n éléments distincts, combien de groupes différents de taille k pouvez-vous former lorsqu'aucun élément n'apparaît deux fois et que l'ordre de sélection n'importe pas ? Cette quantité est le coefficient binomial C(n,k), aussi noté n parmi k. Il n'y a ni échantillonnage, ni réseau, ni arrondi dépendant de la date : chaque couple valide (n, k) produit le même entier à chaque fois.

Ce que dénombrent les combinaisons sans répétition

Les combinaisons sans répétition dénombrent le nombre de façons de choisir un sous-ensemble de k éléments dans un ensemble de n éléments distincts lorsque chaque élément apparaît au plus une fois et que l'ordre de sélection n'importe pas. En classe on dit n parmi k ; en notation statistique c'est le coefficient binomial C(n,k). L'identité classique affirme que C(n,k) vaut la factorielle de n divisée par la factorielle de k multipliée par la factorielle de (n moins k).

Cette même quantité apparaît comme coefficient dans le développement binomial de (x plus y) à la puissance n, et comme le nombre de k-sous-ensembles d'un ensemble à n éléments. Puisque l'ordre est ignoré, choisir Alice puis Bob est la même combinaison que choisir Bob puis Alice, si bien que le décompte est strictement plus petit que la permutation correspondante P(n,k) dès que k vaut au moins deux.

Puisque la répétition est interdite, vous ne pouvez pas tirer la même personne deux fois : c'est la différence avec les combinaisons avec répétition, aussi appelées combinaisons de multiensembles, dont le décompte est C(n+k−1, k). Les cas limites font partie de la définition : C(n,0) et C(n,n) valent tous deux un, C(n,1) égale n, et C(0,0) vaut un par la convention du produit vide.

Si k est plus grand que n, il n'existe pas de k-sous-ensemble d'un n-ensemble, aussi cette calculatrice refuse le couple plutôt que de renvoyer zéro ou un binomial généralisé. L'implémentation ne tire jamais d'échantillon, ne dépend jamais de l'horloge et n'arrondit jamais : elle évalue le produit réduit de (n moins k plus un) jusqu'à n, divisé pas à pas par un jusqu'à k, avec une arithmétique BigInt exacte afin que les grands coefficients restent des entiers précis au lieu de déborder la mantisse d'un flottant.

Usages en classe, échantillonnage et concours

Les enseignants de statistique recourent aux combinaisons sans répétition pour introduire l'échantillonnage sans remise : le nombre de comités distincts de k personnes dans une classe de n, le nombre de mains de k cartes dans un jeu de 52, ou le nombre de façons de tirer k unités défectueuses dans un lot de n pour un schéma hypergéométrique.

Ces problèmes partagent le même entier C(n,k) ; cette page s'adresse à ceux qui cherchent cette expression explicitement, y compris les apprenants à qui l'on vient de dire de ne pas la confondre avec des combinaisons qui autorisent les répétitions. Les générateurs d'examens peuvent figer le chemin de succès avec n égal à dix et k égal à trois, qui donne cent vingt, et le chemin de rejet avec tout k qui dépasse n, qui doit échouer plutôt que renvoyer zéro.

Les programmeurs de concours et les sandboxes d'entretien ont besoin d'un oracle exact pour les problèmes de dénombrement de combinaisons sans réimplémenter une arithmétique multiprécision dans chaque harnais de langage. Des pages sœurs peuvent viser les permutations, les combinaisons avec répétition ou une calculatrice nCr générique ; cet atterrissage est spécifiquement le libellé sans répétition. Associez le décompte à votre propre code d'énumération si vous avez besoin des sous-ensembles eux-mêmes ; cette capacité ne renvoie que l'entier.