Combinaisons avec répétition

Les combinaisons avec répétition ressemblent aux combinaisons classiques, à une différence près : les éléments de l’ensemble de base M peuvent se répéter.

Définition et formule

Commençons par un bel exemple : tu entres dans un magasin et tu veux acheter douze bouteilles de bière pour une randonnée. Le rayon propose quatre marques différentes. Tu as plusieurs possibilités : tu peux par exemple acheter 5 Pilsner, 2 Gambrinus, 1 Staropramen et 4 Kozel, ou acheter exactement trois bouteilles de chaque marque. Combien de choix différents existe-t-il pour acheter exactement douze bouteilles ?

Nous avons donc un ensemble de base M = {Pilsner ; Gambrinus ; Staropramen ; Kozel}, et l’on se demande combien il existe de k-uplets, avec k = 12, contenant des éléments de M et pour lesquels l’ordre n’a pas d’importance.

Établir la formule est un peu plus délicat que pour les autres problèmes de dénombrement. On commence par représenter notre achat par une suite de zéros et de uns : le nombre de uns correspond au nombre de bouteilles achetées de chaque marque, et un zéro sépare les marques. Ainsi, 111011101111101 signifie que nous avons acheté trois Pilsner (les trois premiers 1), puis trois Gambrinus (le 0 sert de séparateur, puis trois 1), puis cinq Staropramen (un 0 séparateur, puis cinq 1) et enfin un Kozel. Le schéma suivant illustre ce principe :

$$\underset{Pil}{\underbrace{111}}0\underset{Gam}{\underbrace{111}}0\underset{Star}{\underbrace{11111}}0\underset{Koz}{\underbrace{1}}$$

Si l’on voulait acheter 6 Pilsner, 4 Gambrinus, 2 Kozel et aucun Staropramen, la suite serait :

$$\underset{Pil}{\underbrace{111111}}0\underset{Gam}{\underbrace{1111}}00\underset{Koz}{\underbrace{11}}$$

Remarquons que la longueur de cette suite vaut toujours 15 : il doit y avoir 12 uns, pour acheter 12 bouteilles au total, et trois séparateurs, pour distinguer quatre marques différentes. Il reste donc à calculer combien il existe de suites de longueur 15 contenant exactement trois zéros.

Il suffit de calculer les positions des zéros : dès que l’on répartit 3 zéros parmi les 12 uns, on obtient une combinaison valide de bouteilles. Autrement dit, on dispose de 15 cases, et il faut en occuper 3 avec un zéro. Les cases restantes sont automatiquement occupées par des uns.

Il s’agit là d’un problème simple de combinaisons sans répétition. On numérote les 15 cases {1 ; … ; 15} et l’on choisit à chaque fois un triplet de numéros, ce qui donne trois indices où placer les zéros. Par exemple, pour la combinaison {2 ; 4 ; 7}, on obtient la suite 101011011111111 : il y a un zéro aux 2ᵉ, 4ᵉ et 7ᵉ positions, les autres chiffres sont des uns. Il existe donc au total

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

façons de répartir les zéros dans les 15 cases, et donc 455 possibilités différentes d’acheter 12 bouteilles lorsque l’on dispose de quatre marques différentes.

Généralisons ce raisonnement. Si l’on a un ensemble M de n éléments et que l’on choisit dans cet ensemble des k-uplets, les éléments pouvant se répéter, on forme une suite de zéros et de uns de longueur n + k − 1 (k uns et n − 1 zéros), et l’on calcule de combien de façons on peut placer les n − 1 zéros. Le nombre de combinaisons avec répétition vaut donc

$$(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

Nous avons pu faire cette dernière simplification grâce aux relations de base entre coefficients binomiaux.

Exercices corrigés

1. De combien de façons peut-on répartir 20 billets gratuits pour la première d’un film entre 10 retraitées ? C’est un exemple de combinaisons avec répétition, car une même retraitée peut en recevoir plusieurs, voire tous. Il faut bien identifier n et k. En réalité, on choisit des combinaisons de 20 éléments parmi 10 retraitées : autrement dit, on forme une suite de zéros et de uns de longueur 29, contenant 20 uns et 9 zéros. Donc n = 10, k = 20. On obtient le résultat :

   $$(\genfrac{}{}{0ex}{}{10+20-1}{20})=10015005.$$