Combinaison avec répétition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Première approche

En mathématiques, lorsque nous choisissons k objets parmi n objets discernables, chaque objet pouvant être répété (au plus k fois), nous obtenons un groupement non ordonné de k objets éventuellement répétés. Mais ce n’est pas acceptable en mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que...) de définir une k-combinaison avec répétition de cette façon, puisqu'un tel groupement n'est pas un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui...) (en effet la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) en extension d'un ensemble empêche la répétition des éléments et par exemple {1, 1, 2, 2, 2, 3}={1, 2, 3})..

Définition :

Une k-combinaison avec répétition d'un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) E de cardinal n, est une application f de E dans {0, 1, ..., k}, telle que

\sum_{x\in E}f(x)=k.

Plus précisément, si E={x1, x2, ..., xn} alors f vérifie

f(x_1)+f(x_2)+\ldots+f(x_n)=k.

f s'appelle aussi une combinaison (Une combinaison peut être :) de n éléments pris k à k.

Remarque :

Cette application indique pour chaque élément de E le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de fois qu'il est choisi; et si l'application associe la valeur 0 à un élément de E, alors l'élément n'est pas choisi. De plus la somme des nombres de répétitions doit bien être égale à k, si nous voulons exactement k objets éventuellement répétés.

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 blanc (Le blanc est la couleur d'un corps chauffé à environ 5 000 °C (voir l'article Corps noir). C'est la sensation visuelle obtenue avec un spectre lumineux continu,...), est représenté par l'application f définie par

f(blanc)=2, f(1)=0, f(2)=0, f(3)=0, f(4)=0, f(5)=0 et f(6)=0

et le domino blanc, 1 par l'application f définie par

f(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

Soit n un entier naturel non nul, et soit l'ensemble E={x1, x2, ..., xn}. Munissons E d'une relation d'ordre total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire...) et supposons que

x1 < x2 < ... < xn

À une k-combinaison avec répétition de E, nous associons le k-uplet croissant (au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution...) 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 d'éléments de E (a1, a2, ..., ak), c'est-à-dire un k-uplet tel que

a1 ? a2 ? ... ? 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 (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel...) 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}.

Nombre de combinaisons avec répétition

Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est...) :

Soit E un ensemble fini de cardinal n (n \in \mathbb N^*). Alors l'ensemble Kk(E) des k-combinaisons avec répétition de E est fini et son cardinal est égal à

\Gamma_n^k=C_{n+k-1}^k,

qui est le nombre de k-combinaisons de n+k-1 éléments.

\Gamma_n^k se lit " Gamma nk ".

Démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir...) :

Les combinaisons avec répétition sont des applications d'un ensemble fini dans un autre ensemble fini donc Kk(E) est fini. Supposons que E={x1, x2, ..., xn}. L'ensemble Kk(E) se partitionne en l'ensemble K' des combinaisons qui envoient x1 sur 0 (représentées par un k-uplet croissant dans lequel x1 n'apparaît pas) et l'ensemble \overline{K'} des combinaisons qui envoient x1 sur un entier naturel non nul (représentées par un k-uplet croissant dans lequel x1 apparaît au moins une fois). En restreignant une combinaison de K' à F=E\{x1} (ce qui revient à la considérer comme un k-uplet croissant d'éléments de F), nous voyons qu'il y a autant d'éléments dans K' que de combinaisons avec répétition de n-1 éléments pris k à k donc \rm{card}(K')=\Gamma_{n-1}^{k}. En retranchant 1 à la valeur en x1 d'une combinaison de \overline{K'} (ce qui revient à " éliminer un x1 " du k-uplet correspondant pour obtenir un (k-1)-uplet), nous transformons cette combinaison en une combinaison avec répétition de n éléments pris k-1 à k-1. Réciproquement, en ajoutant 1 à la valeur en x1 d'une combinaison de n éléments pris k-1 à k-1, nous obtenons un élément de \overline{K'}.
Il y a donc autant d'éléments dans \overline{K'} que de combinaisons avec répétition de n éléments pris k-1 à k-1 donc \rm{card}(\overline{K'})=\Gamma_{n}^{k-1}.
En écrivant

\rm{card}(K_k(E))=\rm{card}\left(\overline{K'}\cup K'\right)=\rm{card}(\overline{K'})+\rm{card}(K'),

nous obtenons la formule de récurrence

\Gamma_n^k=\Gamma_n^{k-1}+\Gamma_{n-1}^k

De plus nous avons pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) entier naturel n non nul, et pour tout entier naturel k \Gamma_n^1=n et \Gamma_1^k=1, et nous en déduisons le résultat.

Autre démonstration :

Nous avons vu qu'il y avait une bijection entre l'ensemble des k-combinaisons avec répétition d'un ensemble E et l'ensemble des applications croissantes de F={1, 2, ..., k} dans E. Il suffit donc de déterminer le cardinal de ce dernier ensemble que nous noterons \mathcal A_c(F, E).

Théorème :

Soient n et k deux entiers naturels non nuls, E un ensemble totalement ordonné (Soit E un ensemble muni d'une relation d'ordre . Rappelons que toute relation d'ordre vérifie les propriétés suivantes:) fini de cardinal n, et F={1, 2, ..., k}. Alors l'ensemble \mathcal A_c(F, E) des applications croissantes de F dans E est fini et son cardinal est le nombre de k-combinaisons avec répétition de E, égal à C_{n+k-1}^k. Et ce cardinal se note \Gamma_n^k.

Démonstration :

Sans perte de généralité, nous pouvons supposer que E={1, 2, ..., n}. Nous allons transformer une application croissante de F dans E en une application strictement croissante de F dans une autre ensemble G, en lui ajoutant l'application x ? x – 1.
Posons G={1, 2, ..., n+k-1} et notons \mathcal A_{sc}(F, G) l'ensemble des applications strictement croissantes de F dans G. À une application croissante f de F dans E, associons l'application g de F dans G définie par

xF, g(x)=f(x)+x-1

Il est facile de vérifier que l'application

\begin{matrix}\varphi : & \mathcal A_{c}(F, E) & \longrightarrow & \mathcal A_{sc}(F, G)\\& f & \longmapsto & (g: x\mapsto f(x)+x-1)\end{matrix}

est bien définie. Et l'application

\begin{matrix}\psi : & \mathcal A_{sc}(F, G) & \longrightarrow & \mathcal A_{c}(F, E)\\& f & \longmapsto & (g: x\mapsto f(x)-x+1)\end{matrix}

est l'application réciproque (En mathématiques, une application réciproque est en des termes simples une fonction qui « fait exactement l'inverse de ce que fait une application...) de ?.

D'où \rm{card}(\mathcal A_{c}(F, E))=\rm{card}(\mathcal A_{sc}(F, G))=C_{n+k-1}^k.

Approche moins "matheuse" des combinaisons avec répétitions

Une combinaison avec répétitions de "k" objets pris parmi "n" objets est une manière de sélectionner "k" objets parmi "n" objets distincts, sans tenir compte de l'ordre des "k" objets et avec répétitions, c’est-à-dire que le même objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est...) peut être sélectionné plusieurs fois.

Le nombre de combinaisons avec répétitions de "k" objets pris parmi "n" objets égale :
C_{n+k-1}^k=\frac{(n+k-1)!}{k! \cdot (n-1)!}

Voici deux démonstrations de cette affirmation.

Première démonstration :
Numérotons les "n" objets de 0 à (n-1).
Remarquez qu'à chaque combinaison avec répétitions de "k" objets parmi les "n", correspond une et une seule permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans...) avec répétitions de "n-1" boules noires et "k" boules blanches.
Le nombre de boules noires à gauche de la première boule blanche correspond au numéro d'un objet de la combinaison avec répétitions.
Le nombre de boules noires à gauche de la deuxième boule blanche correspond au numéro d'un objet de la combinaison avec répétitions.
etc. pour toutes les boules blanches.
Conclusion :
Le nombre de combinaisons avec répétitions de "k" objets pris parmi "n" objets égale le nombre de permutations avec répétitions de "k" boules blanches et de "n-1" boules noires.
Ce nombre vaut : C_{n+k-1}^k=\frac{(n+k-1)!}{k!\cdot(n-1)!}
C'est le nombre de permutations des (n+k-1) boules, mais dans lesquelles on ne distingue pas les permutations des boules noires entre elles et des boules blanches entre elles.
On à (n+k-1)! permutations des boules, qu'il faut diviser par les (n-1)! permutations des boules noires et les k! permutations des boules blanches.

Deuxième démonstration :
Numérotons les "n" objets de 0 à (n-1).
Plaçons n boules noires numérotées de 0 à (n-1) et (k-1) boules blanches dans une urne.
Sur la première boule blanche est noté : "remplacez-moi par une boule noire identique à la plus à gauche".
Sur la deuxième boule blanche est noté : "remplacez-moi par une boule noire identique à la deuxième la plus à gauche".
Sur la troisième boule blanche est noté : "remplacez-moi par une boule noire identique à la troisième la plus à gauche".
etc.
On tire de l'urne "k" boules parmi les "n+k-1" boules noires et blanches. On les place par ordre des numéros sur les boules.
Le nombre de résultats possibles de l'expérience précédente est égal au nombre de combinaisons avec répétitions de "k" objets pris parmi "n" objets.
Il est également égal au nombre de combinaisons sans répétitions de "k" boules parmi les "n+k-1" boules noires et blanches.

Ce nombre est : C_{n+k-1}^k=\frac{(n+k-1)!}{k!\cdot(n-1)!}

Voyez également

  • Combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les...)
  • Combinaison
Page générée en 0.064 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique