Combinatoire/Combinaisons avec répétition

Début 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.

fin de la boite de navigation du chapitre

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$.