Combinaisons de K parmi N

Une combinaison de $ k $ parmi $ n $ est le nom donné au nombre de façons distinctes de choisir $ k $ éléments parmi autre un ensemble de $ n $ éléments (avec $ n \ge k $), sans tenir compte de l'ordre.

La combinaison se note $ C_n^k $ ou $ \binom{n}{k} $.

Le générateur permet de choisir les valeurs de $ k $ et $ n $, et génère les listes de combinaisons possibles correspondantes avec des chiffres ou des lettres (ou encore une liste personnalisée).

La génération est limitée à quelques milliers de combinaisons. L'algèbre combinatoire pouvant introduire de très grands nombres, cette limite permet de ne pas surcharger le serveur.

Pour des générations de listes importantes, dCode propose des prestations de service sur devis.

Le calcul a effectuer utilise la loi binomiale et le coefficient binomial suivant : $$ C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

Les combinaisons utilisent des calculs de factorielles (le point d'exclamation !).

Le principe des combinaisons est de ne pas tenir compte de la notion d'ordre (1,2) = (2,1). Utiliser les permutations pour obtenir des combinaisons ordonnées possibles.

dCode propose un outil dédié pour les combinaisons avec répétitions.

Pour calculer les probabilités de gains dans les jeux de hasard comme les jeux de tirage au sort, les combinaisons sont les outils les plus adaptés.

Pour gagner au loto français, avant 2008, consistait en un tirage de 6 boules parmi 49.

Pour gagner au loto français, après 2008, le tirage est de 5 boules parmi 49, puis 1 boule parmi 10.

Pour gagner à l'EuroMillions, le tirage est de 5 boules parmi 50, puis 2 étoiles parmi 12.

Pour gagner à EuroDreams, le tirage est de 6 numéros parmi 40, puis 1 numéro parmi 5.

De nombreux livres décrivent des stratégies pour les tirages au sort comme ici (lien affilié) Une des stratégies est de jouer des systèmes réducteurs.

Si $ k = 0 $ alors 0 élément sont demandés, il n'y a un unique résultat vide. Ainsi $$ \binom{n}{0} = 1 $$

Si $ n = 0 $ alors il n'y a 0 élément, impossible d'en prendre $ k $, donc il n'y a pas de résultats. Donc $$ \binom{0}{k} = 0 $$

Par convention 0 parmi 0 vaut 1 : $$ \binom{0}{0} = 1 $$

// pseudo code
debut denombrement_combinaisons( k , n ) {
si (k = n) retourner 1;
si (k > n/2) k = n-k;
res = n-k+1;
pour i = 2 par 1 tant que i < = k
res = res * (n-k+i)/i;
fin pour
retourner res;
fin// langage C
double factorielle(double x) {
double i;
double result=1;
if (x >= 0) {
for(i=x;i>1;i--) {
result = result*i;
}
return result;
}
return 0; // erreur
}
double compter_combinaisons(double x,double y) {
double z = x-y;
return factorielle(x)/(factorielle(y)*factorielle(z));
}<code><br>// Langage VBA<br>Function Factorielle(n As Integer) As Double<br> Factorielle = 1<br> For i = 1 To n<br> Factorielle = Factorielle * i<br> Next<br>End Function<br>Function NbCombinaisons (k As Integer, n As Integer) As Double<br> Dim z As Integer<br> z = n - k<br> NbCombinaisons = Factorielle(n) / (Factorielle(k) * Factorielle(z))<br>End Function<br></code>

// javascript
function combinaisons(a) { // a = new Array(1,2)
var fn = function(n, source, en_cours, tout) {
if (n == 0) {
if (en_cours.length > 0) {
tout[tout.length] = en_cours;
}
return;
}
for (var j = 0; j < source.length; j++) {
fn(n - 1, source.slice(j + 1), en_cours.concat([source[j]]), tout);
}
return;
}
var tout = [];
for (var i=0; i < a.length; i++) {
fn(i, a, [], tout);
}
tout.push(a);
return tout;
}