Analyse combinatoire et dénombrement

Combinaison avec répététions :

Nous avons vu les arrangements, les permutations, avec et sans répétitions, ainsi que les combinaisons sans répétitions et le binôme de Newton. A présent, nous allons voir ce que sont les combinaisons avec répétitions.

La définition est la suivante : Une combinaison de p éléments parmi n est un sous ensemble non ordonné de p éléments parmi n et qui peuvent se répéter.

Essayons d’aborder cette notion avec une approche un peu différente que précédemment.
Il est conseillé pour comprendre cette approche d’avoir vu, dans le chapitre des ensembles et applications, les notions de multi-ensembles, si ce n’est pas le cas, ce n’est pas grave, faisons un rappel rapide :

On appelle un multi-ensemble, tout couple (E,m), ou E est appelé l’ensemble « support », et et m, une fonction de E dans \mathbb{N} qu’on appelle multiplicité.
Expliquons ce que cela implique.

Prenons un exemple simple. Supposons qu’on a un ensemble E dans lequel on a une boule rouge, une boule bleue, une boule jaune et une boule verte. On va définir cet ensemble de la manière suivante :
E=\{Boule~rouge,~Boule~bleue,~Boule~jaune,~Boule~verte\}.

Maintenant, et pour expliquer ceci grossièrement. Supposons une application m, qui prend des éléments de E, et qui fait correspondre ces éléments dans \mathbb{N} à un multi-ensemble A.
Schématisons cela :

On voit, à travers ce schéma, la manière de construire le multi-ensemble A. On prend des éléments de E, et on construit, avec les nombres entiers naturels, un autre ensemble, qui est constitué d’une k-combinaison de l’ensemble E.
Dans notre cas de figure, A=\{m(Boule~rouge)=1,m(Boule~bleue)=1,m(Boule~jaune)=2,m(Boule~verte)=0\}
Il s’agit d’une 4-combinaison avec répétition.

En fait, on se rend compte que ceci est une combinaison d’éléments répétables, tout simplement, on le voit, par exemple dans le fait que la boule jaune apparaît deux fois dans A
On se rend compte également qu’un élément (ou plus), peut ne pas se trouver dans la combinaison, comme c’est le cas dans notre exemple, ou la boule verte n’est pas dans A.

Alors comment exprimer tout ceci au travers d’une formule ?

Prenons un autre exemple, très simple, qui est une approche spécifique, mais intuitive et qui va nous amener à une conclusion qui nous permettra de généraliser…

Prenons un ensemble de trois éléments \{1,2,3\}, et voyons comment on peut schématiser des 3-combinaisons à partir de cet ensemble.
Deux paramètres très important à prendre en compte :
Le premier est qu’il y a des répétitions, un élément peut apparaître plusieurs fois dans la combinaison.
Le deuxième, l’absence d’ordre, nous sommes dans le cas de combinaisons, par conséquent, [i,j]=[j,i], et donc on en retire un des deux.
En prenant cela en compte, il nous reste :

[1,1,1]~~~~~~ooo||
[1,2,3]~~~~~~o|o|o
[1,1,2]~~~~~~oo|o|
[1,2,2]~~~~~~o|oo|
[2,2,2]~~~~~~|ooo|
[1,1,3]~~~~~~oo||o
[1,3,3]~~~~~~o||oo
[3,3,3]~~~~~~||ooo
[2,3,3]~~~~~~|o|oo
[2,2,3]~~~~~~|oo|o

Ce que nous avons fait, c’est fait correspondre schématiquement des combinaisons de notre ensemble avec des ronds et des barres. Les ronds sont les éléments, les barres, des séparateurs.
Par exemple, on voit que dans la première combinaison, on a trois « 1 », qui sont représentés par les 3 ronds, un séparateur, suivi d’un vide, qui représente l’absence de l’élément « 2 », et de même, un autre séparateur pour l’absence de « 3 ».

Il y a plusieurs choses à remarquer :

  • On pourrait remarquer que les 3-uplet que l’on obtient sont le résultat d’une transformation des éléments de E dans \mathbb{N}, et c’est tout à fait le cas, on va donc appeler cette transformation, l’application f de E dans \mathbb{N}.
  • Il y a toujours le même nombre de ronds, on peut donc dire que la somme des éléments d’un k-uplet est toujours égale à n, autrement dit, si on a (x_1,x_2,...,x_n) éléments d’un ensemble E, et f, une application qui prend un élément de E dans \mathbb{N}, alors f(x_1)+f(x_2)+...+f(x_n)=k
    Par exemple, si en réalisant le tirage, on a : [2,2,3]~~~~~~|oo|o, on voit qu’on a f(1)=0, f(2)=2, f(3)=1 et on voit bien que f(1)+f(2)+f(3)=3 et k=3, donc la propriété ci-dessus est vérifiée.
  • Il y a également toujours le même nombre de séparateurs, et il y a une relation entre le nombre d’éléments de E et le nombre de séparateurs d’un k-uplet, laquelle ?
    On voit qu’on a un ensemble à 3 éléments, et qu’on a toujours 2 séparateurs, on va donc postuler qu’on a toujours n-1 séparateurs.

Que peut-on en conclure ? Nous avons comme résultat un k-uplet, donc, nous voulons faire une combinaison de k objets. Parmi combien d’objets ? Cette question est un petit plus velue…
En fait, quand on regarde les résultats qu’on peut avoir, on voit qu’il y a toujours n ronds et (n-1) séparateurs. On voit bien qu’on doit considérer n-1+k ou, autrement dit, n+k-1 objets.

On a donc, en appliquant la formule du coefficient binomial :

C^k_{n+k-1}=\displaystyle{\frac{(n+k-1){!}}{k{!}[(n+k-1)-k]{!}}=\frac{(n+k-1){!}}{k{!}(n-1){!}}}

Cette combinaison avec répétitions à un nom, on l’appelle Gamma nk, et on l’écrit :

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

Publicité
Pages : 1 2 3 4 5 6 7