Combinaison avec répétition

Supposons que E = {x₁, x₂, … , x_n}. Les k-combinaisons de E avec répétition qui ne contiennent pas x₁ sont en bijection avec les k-combinaisons avec répétition de {x₂, … , x_n} donc il y en a ${\displaystyle \Gamma _{n-1}^{k}}$. Les k-combinaisons de E avec répétition qui contiennent x₁ au moins une fois sont en bijection (en leur enlevant un x₁) avec les (k – 1)-combinaisons de E avec répétition donc il y en a ${\displaystyle \Gamma _{n}^{k-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[1] ${\displaystyle \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 ${\displaystyle k}$, ${\displaystyle \Gamma _{1}^{k}=1}$ et pour tout entier n > 0, ${\displaystyle \Gamma _{n}^{0}=1}$.

Les n objets étant numérotés de 1 à n, la k-combinaison avec répétition où le premier objet est choisi k₁ fois, le deuxième k₂ fois, etc. (avec k₁ + k₂ + … + k_n = k) peut être codée par la liste suivante de k étoiles et n – 1 barres verticales : k₁ étoiles, une barre, k₂ étoiles, une barre, … , une barre, k_n étoiles. Par exemple la combinaison avec répétitions ${\displaystyle \{a,a,b,b,b,d\}}$ d'objets pris dans ${\displaystyle \{a,b,c,d\}}$ est codée par ${\displaystyle **\,|***|\,\,|*}$

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[1]

${\displaystyle \Gamma _{n}^{k}={\frac {(n+k-1)!}{k!~(n-1)!}}.}$

Ou encore[2] : c'est le nombre de choix pour les k emplacements des étoiles, parmi les n + k – 1 emplacements de la liste. On trouve alors bien:

${\displaystyle \Gamma _{n}^{k}={n+k-1 \choose k}.}$Cette démonstration, très simple, est une belle application de la démonstration par bijection.

Sans perte de généralité, nous pouvons supposer que E = {1, 2, ..., n} (cela revient à choisir un ordre total sur E).

À une k-combinaison avec répétition f de E, nous associons le k-uplet croissant (au sens large) ${\displaystyle {\begin{matrix}(\underbrace {1,\ldots ,1} ,&\underbrace {2,\ldots ,2} ,&\ldots ,&\underbrace {n,\ldots ,n} )\\{}_{f(1){\rm {\,fois}}}&{}_{f(2){\rm {\,fois}}}&&{}_{f(n){\rm {\,fois}}}\end{matrix}}.}$ Réciproquement, à un k-uplet croissant (a₁, a₂, … , a_k) d'éléments de E, c'est-à-dire un k-uplet tel que ${\displaystyle a_{1}\leqslant a_{2}\leqslant a_{3}\cdots \leqslant a_{k}}$ 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(1) + f(2) + … + f(n) = 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 a ≤ b d'éléments de E = {blanc, 1, 2, 3, 4, 5, 6}.

Nous venons de voir[3] qu'il y a autant de k-combinaisons de E avec répétition que de k-uplets croissants ${\displaystyle a_{1}\leqslant a_{2}\leqslant a_{3}\cdots \leqslant a_{k}}$ d'éléments de E. En associant, à un tel k-uplet, le k-uplet d'entiers b₁ = a₁ + 0, b₂ = a₂ + 1, … , b_k = a_k + k – 1, on obtient une bijection[4] entre l'ensemble des k-uplets croissants d'éléments de E et l'ensemble des k-uplets strictement croissants ${\displaystyle b_{1}<b_{2}<b_{3}\cdots <b_{k}}$ 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 : ${\displaystyle \Gamma _{n}^{k}={n+k-1 \choose k}.}$

Grâce à cette deuxième représentation avec les inégalités, nous pouvons déduire une nouvelle formule de combinaisons avec répétition pour ${\displaystyle k\geqslant 1}$ et ${\displaystyle n\geqslant 1}$ qui donne lieu à l'identité : ${\displaystyle \Gamma _{n}^{k}={n+k-1 \choose k}=\sum _{a_{k-1}=1}^{n}\sum _{a_{k-2}=1}^{a_{k-1}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1}$

Nous pouvons démontrer cette formule par récurrence ${\displaystyle \forall k\geqslant 1,n\geqslant 1}$:

• L'initialisation pour ${\displaystyle n=1}$ :

${\displaystyle \Gamma _{1}^{k}={1+k-1 \choose k}={k \choose k}=1}$ ${\displaystyle \sum _{a_{k-1}=1}^{1}\sum _{a_{k-2}=1}^{a_{k-1}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1=\sum _{a_{k-2}=1}^{1}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1=\cdots =\sum _{a_{1}=1}^{1}\sum _{a_{0}=1}^{a_{1}}1=\sum _{a_{0}=1}^{1}1=1}$

• Hérédité, supposons la propriété vraie au rang ${\displaystyle n}$, montrons qu'elle est vraie au rang ${\displaystyle n+1}$ :

${\displaystyle \Gamma _{n+1}^{k}={n+1+k-1 \choose k}={n+k \choose k}={n+k-1 \choose k}+{n+k-1 \choose k-1}={n+k-1 \choose k}+{n+1+k-2 \choose k-1}}$ ${\displaystyle \implies \Gamma _{n+1}^{k}=\sum _{a_{k-1}=1}^{n}\sum _{a_{k-2}=1}^{a_{k-1}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1+\sum _{a_{k-2}=1}^{n+1}\sum _{a_{k-3}=1}^{a_{k-2}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1}$ En posant ${\displaystyle x=\sum _{a_{k-3}=1}^{a_{k-2}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1}$ : ${\displaystyle \Gamma _{n+1}^{k}=\sum _{a_{k-1}=1}^{n}\sum _{a_{k-2}=1}^{a_{k-1}}x+\sum _{a_{k-2}=1}^{n+1}x}$ ${\displaystyle \implies \Gamma _{n+1}^{k}=\sum _{a_{k-1}=1}^{n+1}\sum _{a_{k-2}=1}^{a_{k-1}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1}$ Ce qui démontre l'identité mathématique, et donc le pont entre les coefficients binomiaux et les sommes d'une nouvelle manière.

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

• Si l'on écrit in extenso les ${\displaystyle \Gamma _{n}^{k}}$ combinaisons avec répétition de k éléments parmi n, on écrira ${\displaystyle k\times \Gamma _{n}^{k}}$ éléments. Les n éléments jouant un rôle symétrique, chacun apparaîtra donc ${\displaystyle k\times \Gamma _{n}^{k} \over 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 ${\displaystyle \Gamma _{n}^{k}}$ combinaisons avec répétition précédentes, le nombre de celles contenant x (une ou plusieurs fois) est ${\displaystyle \Gamma _{n}^{k-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 ${\displaystyle \Gamma _{n}^{k-1}}$ combinaisons avec répétition contenant au moins une fois x, cela nous assure d'ores et déjà ${\displaystyle \Gamma _{n}^{k-1}}$ apparitions de x. (2)
• Enlevons maintenant une fois x de chacune de ces ${\displaystyle \Gamma _{n}^{k-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 ${\displaystyle (k-1)\Gamma _{n}^{k-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 ${\displaystyle (k-1)\Gamma _{n}^{k-1} \over n}$ fois (3).
• Confrontons nos deux méthodes de calcul : nous avons donc : (1) = (2) + (3), soit${\displaystyle {\frac {k}{n}}\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 :${\displaystyle \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 ${\displaystyle \Gamma _{n}^{0}=1}$.

Le plus efficace et le plus simple, pour calculer le nombre de combinaisons avec répétition, est d'utiliser l'algorithme calculant le nombre de combinaisons sans répétition 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étition est le même que le nombre de combinaisons de k objets parmi n + k – 1 sans répétition.