Combinaison avec répétition

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En combinatoire — le domaine mathématique des dénombrements — une combinaison avec répétition est une combinaison où donc l'ordre des éléments n'importe pas et où, contrairement à une combinaison classique, chaque élément de la combinaison peut apparaître plusieurs fois. Par exemple, si dix dés à six faces (numérotées de 1 à 6) sont jetés, le résultat fourni par ces dix dés, si l'ordre dans lequel sont jetés les dés n'est pas compté, (par exemple un 2, trois 4, deux 5 et quatre 6, sans retenir à quel dé précisément correspond chaque face) est une combinaison des différentes faces apparaissant sur chaque dé, et où chaque face peut apparaître plusieurs fois.

Première approche[modifier | modifier le code]

Une combinaison avec répétition de k objets pris dans un ensemble E = {x1, x2, … , xn} de n objets discernables est une manière de sélectionner k fois de suite un objet dans E, sans tenir compte de l'ordre des k choix et « avec remise », le même objet pouvant donc être sélectionné plusieurs fois. On obtient ainsi un groupement non ordonné de k objets éventuellement répétés : ce groupement n’est pas un ensemble, la définition en extension d'un ensemble empêchant la répétition des éléments, mais un multiensemble. On peut formaliser cela en notant f(k) le nombre de fois (éventuellement nul) que l'élément xk a été choisi, la seule contrainte étant f(x1) + f(x2) + … + f(xn) = k, pour avoir un total de k objets, éventuellement répétés :

Définition — Une k-combinaison avec répétition d'un ensemble fini E de cardinal n, est une application f de E dans {0, 1, ..., k}, telle que \sum_{x\in E}f(x)=k.

f s'appelle aussi une combinaison de n éléments pris k à k.

Exemple
Dans un jeu de dominos, un domino est une 2-combinaison avec répétition de l'ensemble E = {blanc, 1, 2, 3, 4, 5, 6}. Chaque domino peut être représenté par une application de E dans {0, 1, 2} qui associe à chaque élément de E le nombre de fois où l'élément apparaît sur le domino.
Ainsi, le domino tout blanc est représenté par l'application f définie parf(blanc) = 2, f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 0, f(5) = 0 et f(6) = 0et le domino {blanc, 1} par l'application f définie parf(blanc) = 1, f(1) = 1, f(2) = 0, f(3) = 0, f(4) = 0, f(5) = 0 et f(6) = 0.

Une autre représentation[modifier | modifier le code]

Munissons l'ensemble E = {x1, x2, … , xn} de la relation d'ordre total x1 < x2 < … < xn.

À une k-combinaison avec répétition de E, nous associons le k-uplet croissant (au sens large) \begin{matrix}(\underbrace{x_1, \ldots, x_1}, & \underbrace{x_2, \ldots, x_2}, & \ldots, & \underbrace{x_n, \ldots, x_n})\\{}_{f(x_1)\rm{\,fois}} & {}_{f(x_2)\rm{\,fois}} & & {}_{f(x_n)\rm{\,fois}}\end{matrix}. Réciproquement, à un k-uplet croissant (a1, a2, … , ak) d'éléments de E, c'est-à-dire un k-uplet tel que a1a2 ≤ … ≤ ak, nous pouvons associer l'application f : E → {0, 1, … , k} qui envoie un élément de E sur le nombre de fois où il apparaît dans le k-uplet. Il est alors évident que f(x1) + f(x2) + … + f(xn) = k et donc que f est une k-combinaison avec répétition de E.

Ainsi, il y a une bijection entre l'ensemble des k-combinaisons avec répétition de E et l'ensemble des k-uplets croissants d'éléments de E, ou encore des applications croissantes (au sens large) de {1, 2, … , k} dans E.

Exemple
Un domino peut être représenté de manière unique par un couple croissant (a, b) tel que ab d'éléments de E = {blanc, 1, 2, 3, 4, 5, 6}.

Nombre de combinaisons avec répétition[modifier | modifier le code]

Théorème[1] —  Le nombre de k-combinaisons avec répétition d'un ensemble à n éléments (n > 0), noté Γnk (qui se lit « Gamma nk »), est égal à \Gamma_n^k={n+k-1 \choose k}=\frac{(n+k-1)!}{k!~(n-1)!}, qui est le nombre de k-combinaisons (sans répétition) de n + k – 1 éléments.

Première démonstration[modifier | modifier le code]

Supposons que E = {x1, x2, … , xn}. Les k-combinaisons de E avec répétition qui ne contiennent pas x1 sont en bijection avec les k-combinaisons avec répétition de {x2, … , xn} donc il y en a Γn–1k. Les k-combinaisons de E avec répétition qui contiennent x1 au moins une fois sont en bijection (en leur enlevant un x1) avec les (k – 1)-combinaisons de E avec répétition donc il y en a Γnk–1. Le nombre total de k-combinaisons de E avec répétition est la somme de ces deux nombres. On en déduit la relation de récurrence[2] \forall n>1\quad\forall k>0\quad\Gamma_n^k=\Gamma_n^{k-1}+\Gamma_{n-1}^k. Le résultat s'en déduit par récurrence sur n + k, compte tenu du fait que pour tout entier naturel k, Γ1k = 1 et pour tout entier n > 0, Γn0 = 1.

Deuxième démonstration[modifier | modifier le code]

Sans perte de généralité, nous pouvons supposer que E = {1, 2, ..., n}. Nous avons vu qu'il y a autant de k-combinaisons de E avec répétition que de k-uplets croissants a1a2 ≤ … ≤ ak d'éléments de E. En associant, à un tel k-uplet, le k-uplet d'entiers b1 = a1 + 0, b2 = a2 + 1, … , bk = ak + k – 1, on obtient une bijection[3] entre l'ensemble des k-uplets croissants d'éléments de E et l'ensemble des k-uplets strictement croissants b1 < b2 < … < bk d'éléments de {1, 2, ..., n + k – 1}. Or le cardinal de ce nouvel ensemble est le nombre de combinaisons sans répétition de k objets pris parmi n + k – 1, c'est-à-dire le coefficient binomial : \Gamma_n^k={n+k-1\choose k}.

Troisième démonstration[modifier | modifier le code]

Procédons par double dénombrement[4], comme dans la première démonstration ci-dessus.

  • Si l'on écrit in extenso les Γnk combinaisons avec répétition de k éléments parmi n, on écrira k × Γnk éléments. Les n éléments jouant un rôle symétrique, chacun apparaîtra donc k × Γnk/n fois. (1)
    Soit x l'un de ces éléments. Calculons d'une autre manière le nombre de fois où il apparaît.
  • Parmi les Γnk combinaisons avec répétition précédentes, le nombre de celles contenant x (une ou plusieurs fois) est Γnk–1. En effet, x étant imposé au moins une fois, on ne choisit plus que k – 1 éléments, distincts ou non, sans ordre, mais toujours parmi n (car rien n'empêche que x soit répété et donc puisse réapparaître). Chacune de ces Γnk–1 combinaisons avec répétition contenant au moins une fois x, cela nous assure d'ores et déjà Γnk–1 apparitions de x. (2)
  • Enlevons maintenant une fois x de chacune de ces Γnk–1 combinaisons. Chacune d'entre elles ne contient plus à présent que k – 1 éléments (répétés ou non) ; il nous reste donc en tout (k – 1)Γnk–1 éléments. Nous n'avons plus d'hypothèse sur les k – 1 éléments restants dans chaque combinaison avec répétition. Chacun des n éléments (en particulier x) joue donc un rôle symétrique et apparaît donc (k – 1)Γnk–1/n fois (3).
  • Confrontons nos deux méthodes de calcul : nous avons donc : (1) = (2) + (3), soit\frac kn\Gamma_n^k=\Gamma_n^{k-1}+\frac{k-1}{n}\Gamma_n^{k-1}=\frac{n+k-1}{n}\Gamma_n^{k-1}, ce qui nous donne finalement :\Gamma_n^k=\frac{n+k-1}{k}\Gamma_n^{k-1}.

Le résultat s'en déduit par récurrence sur k, compte tenu du fait que Γn0 = 1.

Quatrième démonstration[modifier | modifier le code]

Article détaillé : Étoiles et barres (combinatoire) (en).

Les n objets étant numérotés de 1 à n, la k-combinaison avec répétition où le premier objet est choisi k1 fois, le deuxième k2 fois, etc. (avec k1 + k2 + … + kn = k) peut être codée par la liste suivante de k étoiles et n – 1 barres verticales : k1 étoiles, une barre, k2 étoiles, une barre, … , une barre, kn étoiles.

Le nombre de tels « codes » est égal au nombre de permutations avec répétition des n + k – 1 éléments : k étoiles indiscernables et n – 1 barres indiscernables. Ce nombre est donc le coefficient multinomial[2]

\Gamma_n^k=\frac{(n+k-1)!}{k!~(n-1)!}.

Ou encore[5] : c'est le nombre de choix pour les k emplacements des étoiles, parmi les n + k – 1 emplacements de la liste. On retrouve donc, comme dans la deuxième démonstration ci-dessus :

\Gamma_n^k={n+k-1\choose k}.

Algorithme de dénombrement[modifier | modifier le code]

Le plus efficace et le plus simple, pour calculer le nombre de combinaisons avec répétitions, est d'utiliser l'algorithme calculant le nombre de combinaisons sans répétitions, comme décrit sur la page « Combinaison (mathématiques) ». En effet, comme indiqué ci-dessus, le nombre de combinaisons de k objets parmi n avec répétitions est le même que le nombre de combinaisons de n objets parmi n + k – 1 sans répétitions.

Autres dénombrements équivalents à celui des combinaisons avec répétition[modifier | modifier le code]

Γnk est aussi le nombre de monômes unitaires de degré k formés à partir des n indéterminées X1, X2, … , Xn.

C'est aussi le nombre de dérivées partielles d'ordre k d'une fonction de n variables de classe Ck, compte tenu du théorème de Schwarz qui permet de ne pas tenir compte de l'ordre dans lequel sont effectuées les dérivations (en tenant compte de l'ordre, il y en aurait nk).

Notes et références[modifier | modifier le code]

  1. (en) Eric W. Weisstein, « Multichoose », MathWorld.
  2. a et b Louis Esch, Mathématique pour économistes et gestionnaires, De Boeck,‎ (lire en ligne), p. 21.
  3. A. Bégyn, G. Connan et R. Leroy, Mathématiques Méthodes et Exercices BCPST 1re année, Dunod,‎ , 2e éd. (lire en ligne), p. 226.
  4. Démonstration tirée de P. Louquet et A. Vogt, Probabilités, Combinatoire, Statistiques, Armand Colin,‎ .
  5. Dany-Jack Mercier, L'épreuve d'exposé au CAPES mathématiques, Publibook,‎ (lire en ligne), p. 65.

Lien externe[modifier | modifier le code]

Michel Hort, « Nombre de combinaisons et d’arrangements avec répétitions limitées »