Combinatoire/Combinaisons avec répétition

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Comme prévu nous étudierons ici les combinaisons avec répétition. Une combinaison avec répétition peut être vue comme :

• un tirage avec remise, sans tenir compte de l’ordre, de k objets parmi n objets ;
• une répartition de k objets indiscernables parmi n boîtes discernables pouvant contenir un nombre quelconque d'objets.

Plus formellement, une $k$-combinaison avec répétition dans un ensemble $E$ est un multiensemble de $k$ éléments de $E$ (donc non ordonnés, mais comptés avec leurs répétitions éventuelles, un même élément $x$ pouvant figurer $f(x)$ fois, avec $f(x)\in \mathbb {N}$). Autrement dit :

Définition

Une $k$-combinaison avec répétition dans un ensemble $E$ est une application $f:E\to \mathbb {N}$ telle que $\sum _{x\in E}f(x)=k$.

Début d'un lemme

Lemme

Soit $n\in \mathbb {N} ^{*}$. Le nombre de $n$-uplets d'entiers strictement positifs de somme $m$ est égal à ${\binom {m-1}{n-1}}$.

Fin du lemme

Démonstration

Ces $n$-uplets $(x_{1},\dots ,x_{n})$ sont en bijection avec les $n$-uplets $(y_{1},\dots ,y_{n})$ d'entiers tels que $1\leq y_{1}<y_{2}<\dots <y_{n-1}<y_{n}=m$, par l'application qui à $(x_{1},\dots ,x_{n})$ associe $(x_{1},x_{1}+x_{2},x_{1}+x_{2}+x_{3},\dots ,x_{1}+x_{2}+\dots +x_{n})$.

Ces $n$-uplets $(y_{1},\dots ,y_{n})$ sont eux-mêmes en bijection avec les parties de cardinal $n-1$ de l'ensemble $\{1,2,\dots ,m-1\}$, par l'application qui à $(y_{1},\dots ,y_{n})$ associe l'ensemble $\{y_{1},\dots ,y_{n-1}\}$.

Il y en a donc bien ${\binom {m-1}{n-1}}$.

 

Remarque : ce nombre est non nul si et seulement si $m\geq n$.

Début d’un théorème

Théorème

Soit $n\in \mathbb {N} ^{*}$.

1. Le nombre de $n$-uplets d'entiers positifs ou nuls de somme $k$ est égal à ${\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}$.
2. Pour tout ensemble fini $E$ de cardinal $n$, le nombre de $k$-combinaisons avec répétition dans $E$ est égal à ce même nombre.

Fin du théorème

Démonstration

1. Ces $n$-uplets $(z_{1},\dots ,z_{n})$ sont en bijection avec les $n$-uplets $(x_{1},\dots ,x_{n})$ d'entiers strictement positifs de somme $n+k$, en posant $x_{i}=z_{i}+1$. D'après le lemme, il y en a donc bien ${\binom {n+k-1}{n-1}}$.
2. Sans perte de généralité, $E=\{1,2,\dots ,n\}$. Les $k$-combinaisons avec répétition dans $E$ sont alors exactement les $n$-uplets d'entiers positifs ou nuls de somme $k$.

 

Remarque : ce nombre est non nul si et seulement si $m\geq n$.