Une combinaison est une selection non ordonnee d'elements d'un ensemble, tandis qu'un arrangement (parfois appele permutation partielle) est une selection ordonnee. Si vous tirez 3 cartes d'un jeu et que vous tenez compte de la carte sortie en premier, deuxieme et troisieme, vous comptez des arrangements : as-roi-dame et dame-roi-as sont differents. Si seul l'ensemble final de 3 cartes vous interesse, vous comptez des combinaisons : les deux tirages donnent la meme main. Formellement, le nombre d'arrangements de k elements parmi n est A(n,k) = n! / (n-k)!, et le nombre de combinaisons est C(n,k) = n! / (k!(n-k)!). Les deux formules different du facteur k! qui compte les ordres possibles d'un meme sous-ensemble, donc A(n,k) vaut toujours k! fois C(n,k).

Demandez-vous si echanger deux des elements choisis produit un resultat que l'enonce considere comme different. Si oui, utilisez les arrangements ; sinon, utilisez les combinaisons. Le podium d'une course (or, argent, bronze) est un arrangement car les medailles sont distinctes. Une commission de 3 personnes est une combinaison car ses membres restent les memes quel que soit l'ordre de nomination. Les mots de passe et codes PIN sont des arrangements car 1234 et 4321 ouvrent des comptes differents. Les numeros tires au Loto FDJ sont des combinaisons car le bulletin est gagnant quel que soit l'ordre d'inscription des numeros. En cas de doute, listez un cas simple a la main et verifiez que votre comptage coincide avec la formule.

En France, le programme officiel de l'Education nationale utilise plusieurs notations. Pour les combinaisons, la notation moderne (depuis la reforme des programmes de lycee) est le coefficient binomial \binom{n}{k}, qui se lit 'k parmi n'. L'ancienne notation francaise C_n^k (avec n en bas et k en haut) reste tres repandue dans les manuels et les concours. Pour les arrangements, la notation francaise standard est A_n^k (lue 'A n k'), tandis que la notation anglo-saxonne P(n,k) ou nPr est plus rare dans les copies francaises. Attention : les conventions d'indices different selon les pays. En notation francaise C_n^k, n est l'ensemble total et k la taille du sous-ensemble. En notation anglo-saxonne C(n,k) ou nCr, l'ordre des arguments est inverse. Le calculateur affiche C(n,r) et P(n,r) suivant la convention internationale, mais les formules sont equivalentes.

Le Loto de la Francaise des Jeux (FDJ) demande de cocher 5 numeros parmi 49 plus 1 numero chance parmi 10. Le nombre de grilles possibles est donc C(49,5) x 10 = 1 906 884 x 10 = 19 068 840. La probabilite de gagner le rang 1 (jackpot) avec une seule grille est 1 / 19 068 840, soit environ 1 chance sur 19 millions. L'EuroMillions demande 5 numeros parmi 50 plus 2 etoiles parmi 12. Le nombre de combinaisons est C(50,5) x C(12,2) = 2 118 760 x 66 = 139 838 160, soit environ 1 chance sur 140 millions de gagner le jackpot avec une seule grille. Deux conclusions pratiques : acheter plusieurs grilles n'augmente les chances que de facon lineaire (10 grilles a l'EuroMillions donnent toujours environ 1 chance sur 14 millions), et l'esperance mathematique d'une grille est presque toujours negative une fois les impots et les jackpots partages pris en compte.

La factorielle n! = n x (n-1) x ... x 1 compte le nombre de facons d'ordonner n elements distincts en ligne, ce qui constitue la brique de base des formules de combinaisons et d'arrangements. Les factorielles croissent extremement vite : 10! vaut deja 3 628 800, 20! depasse 2,4 x 10^18, et 70! depasse la capacite d'un nombre flottant standard sur 64 bits. C'est pourquoi les calculateurs doivent simplifier les facteurs communs avant de multiplier. Pour C(100,3), evaluer directement 100! / (3! x 97!) est inefficace, mais reecrire ce calcul comme (100 x 99 x 98) / (3 x 2 x 1) = 161 700 est rapide et exact. La plupart des outils combinatoires bien concus utilisent cette simplification ou les logarithmes de factorielles en interne.

Le triangle de Pascal, etudie par Blaise Pascal au XVIIe siecle, est une table de consultation directe des coefficients binomiaux : l'entree de la ligne n a la position k (indexee a partir de zero) vaut exactement C(n,k). La ligne 5 se lit 1, 5, 10, 10, 5, 1, qui sont C(5,0) a C(5,5). La regle de construction du triangle (chaque entree est la somme des deux entrees au-dessus) correspond a l'identite de Pascal : C(n,k) = C(n-1,k-1) + C(n-1,k), qui a une preuve combinatoire elegante : un sous-ensemble de taille k parmi n contient soit le n-ieme element (alors on choisit les k-1 restants parmi n-1), soit ne le contient pas (alors on choisit les k parmi les n-1 premiers). Le triangle encode aussi la formule du binome de Newton, car les entrees de la ligne n sont les coefficients du developpement de (a+b)^n.

n et k doivent etre des entiers positifs ou nuls, et k doit etre inferieur ou egal a n pour les formules standard (sans remise). Les cas particuliers sont bien definis : C(n,0) = 1 car il existe exactement une facon de ne rien choisir (l'ensemble vide), C(n,n) = 1 car il existe une facon de tout choisir, A(n,0) = 1 par convention, et 0! = 1 pour que les formules restent coherentes. Si votre probleme produit un n non entier, un k negatif ou un k superieur a n, le comptage standard est indefini ou nul, et il faut reexaminer si le probleme demande un autre modele comme les coefficients multinomiaux, les permutations avec repetition ou les combinaisons avec remise.

Sans remise, chaque element ne peut etre choisi qu'au plus une fois, ce qui est l'hypothese par defaut des formules standard A(n,k) et C(n,k). Avec remise, le meme element peut etre choisi plusieurs fois, ce qui augmente les comptages. Les arrangements avec remise valent simplement n^k, car chacune des k positions dispose des n options. Les combinaisons avec remise utilisent la formule des etoiles et des barres C(n+k-1, k), qui compte les multi-ensembles. Par exemple, le nombre de facons de choisir 3 boules de glace parmi 5 parfums lorsque les repetitions sont autorisees est C(5+3-1, 3) = C(7,3) = 35. Indices pratiques : tirer des cartes sans les remettre est sans remise, tandis que lancer un meme de k fois est avec remise.