Combinaison (mathématiques)

Les combinaisons sont un concept de mathématiques, plus précisément de combinatoire, décrivant les différentes façons de choisir un nombre donné d'objets dans un ensemble de taille donnée, lorsque les objets sont discernables et que l'on ne se soucie pas de l'ordre dans lequel les objets sont placés ou énumérés.

Contrairement aux arrangements, les combinaisons s'intéressent uniquement aux éléments choisis parmi l'ensemble, et non à l'ordre dans lequel ils sont tirés. Un exemple est la main obtenue en tirant simultanément $k$ cartes dans un jeu de $n$ cartes. Dans ce cas, l'ordre des cartes n'est pas important pour le joueur pour élaborer sa stratégie. De même pour le jeu du loto, l'ordre de tirage des 6 boules parmi les 49 n'est pas pris en compte pour gagner. Le tirage final est alors vu comme un ensemble non ordonné de 6 numéros.

Les combinaisons sont utilisées, entre autres, en dénombrement et en probabilités, notamment dans le cadre des tirages.

Combinaison sans répétition

Si la précision n'est pas donnée, on parle généralement de combinaison sans répétition. Le nom complet, bien que peu usité est combinaison sans répétition de $n$ éléments pris $k$ à $k$. Autrement dit, les combinaisons de taille $k$ d'un ensemble $E$ de cardinal $n$ sont les sous-ensembles de $E$ qui ont pour taille $k$.

Définition

Soit $E$ un ensemble fini de cardinal $n$ et $k$ un entier naturel. Les combinaisons de cet ensemble sont ses sous-ensembles (ou ses parties).

Une k-combinaison de E (ou k-combinaison sans répétition de E, ou encore combinaison sans répétition de n éléments pris k à k) est une partie à k éléments de E.

On note ${\mathcal {P}}_{k}(E)$ l’ensemble des $k$-combinaisons de E.

Nombre de combinaisons

L’ensemble ${\mathcal {P}}_{k}(E)$ est fini et son cardinal est le coefficient binomial ${n \choose k}$, aussi noté $C_{n}^{k}$. On a :

$C_{n}^{k}={n \choose k}={\frac {A_{n}^{k}}{k!}}$,

où $A_{n}^{k}$ est le nombre de $k$-arrangements de $E$ et $k!$ est la factorielle de $k$.

Avec la formule pour $A_{n}^{k}={\frac {n!}{(n-k)!}}$, on obtient ${n \choose k}={\frac {n(n-1)\ldots (n-k+1)}{k!}}$, qui pour $k\leqslant n$ peut aussi s'écrire :

${n \choose k}={\frac {n!}{k!(n-k)!}}$.

Calcul du nombre de combinaisons

Un algorithme efficace pour calculer le nombre ${\binom {n}{k}}$ de combinaisons de $k$ éléments parmi $n$, utilise les identités suivantes ($0\leqslant k\leqslant n$) :

${\binom {n}{k}}={\binom {n}{n-k}}$,         ${\binom {n+1}{k+1}}={\frac {n+1}{k+1}}{\binom {n}{k}}$     et     ${\binom {n}{0}}=1$.

La première permet de réduire le nombre d'opérations à effectuer en se ramenant à $k\leqslant n/2$. Les deux suivantes permettent de montrer que :

${\binom {n}{k}}={\frac {(n-k+1)}{1}}\cdot {\frac {(n-k+2)}{2}}\cdot \cdots \cdot {\frac {n}{k}}$

À chaque étape de calcul on effectue d'abord la multiplication puis la division pour obtenir un nombre entier (c'est un coefficient binomial), c'est-à-dire que l'on peut employer la division entière. Les calculs intermédiaires restent d'un ordre de grandeur voisin du résultat final (ce ne serait pas le cas si par exemple on utilisait la première formule et la fonction factorielle).

Le calcul peut s'effectuer par une simple boucle itérative (boucle for).

Exemple

${\binom {10}{7}}=?\quad 10-7=3<7,\quad {\binom {7}{0}}=1\Rightarrow {\binom {8}{1}}={\frac {8}{1}}\times 1=8\Rightarrow {\binom {9}{2}}={\frac {9}{2}}\times 8=36\Rightarrow {\binom {10}{3}}={\frac {10}{3}}\times 36=120\Rightarrow {\binom {10}{7}}=120.$

Pour de grandes valeurs de n et de k, il est souvent plus pratique d'utiliser les formules approchées suivantes (on en trouvera les justifications et d'autres plus détaillées dans l'article coefficient binomial) :

${n \choose k}\sim n^{k}/k!$ (pour k fixé et n tendant vers l'infini) et (si n et k tendent vers l'infini avec $k/n\rightarrow \alpha \in ]0;1[$) ${\binom {n}{k}}{\sim }{\frac {1}{\sqrt {2\pi \alpha (1-\alpha )n}}}\left({\frac {1}{\alpha ^{\alpha }(1-\alpha )^{1-\alpha }}}\right)^{n}$.

Énumération des combinaisons

Soient A un ensemble à n éléments, a un objet qui n'est pas dans A, et k un entier naturel. Alors pour former les parties de $A\cup \{a\}$ ayant k + 1 éléments, on forme les parties de k + 1 éléments de A, ainsi que les parties de k éléments de A auxquelles on adjoint {a}. Autrement dit :

${\mathcal {P}}_{k+1}(A\cup \{a\})={\mathcal {P}}_{k+1}(A)\cup \left\{X\cup \{a\}\mid X\in {\mathcal {P}}_{k}(A)\right\}$         (${\mathcal {P}}_{k}(A)=\varnothing$ si k > n)

(cette identité a pour conséquence directe la formule de récurrence permettant de construire le triangle de Pascal : ${\tbinom {n+1}{k+1}}={\tbinom {n}{k+1}}+{\tbinom {n}{k}}$). Cette identité peut être exploitée pour un algorithme énumérant les combinaisons, par exemple des n premiers entiers.

Exemples

Soit A l'ensemble de 5 éléments A = {a, b, c , d, e}.

• Les combinaisons de 2 éléments parmi les 5 sont :
  • celles qui contiennent deux éléments distincts de a : {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e},
  • celles qui contiennent a et un autre élément : {a, b}, {a, c}, {a, d}, {a, e},
    soit${5 \choose 2}={4 \choose 2}+{4 \choose 1}=6+4=10.$
• Les combinaisons de 3 éléments choisis parmi les 5 éléments de A sont :
  • celles qui contiennent a et deux autres éléments : {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e},
  • celles qui contiennent trois éléments distincts de a : {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e},
    soit${5 \choose 3}={4 \choose 2}+{4 \choose 3}=6+4=10.$.
    Ce sont en fait les complémentaires des combinaisons précédentes.

Combinaison avec répétition

Représentations de toutes les combinaisons avec répétition de trois éléments pris parmi 5

Contrairement à une combinaison classique (sans répétition), chaque élément de la

combinaison peut apparaître plusieurs fois.

Par exemple, lorsque dix dés à six faces (numérotées de 1 à 6) sont jetés, le résultat fourni par ces dix dés, si l'ordre dans lequel sont jetés les dés n'est pas pris en compte, est une combinaison de 10 éléments pris parmi les 6 faces possibles des dés, où chaque face peut apparaître plusieurs fois. On peut ainsi obtenir, par exemple, un 2, trois 4, deux 5 et quatre 6, soit la combinaison 2,4,4,4,5,5,6,6,6,6.

Première approche

Une combinaison avec répétition de k objets pris dans un ensemble E = {x₁, x₂, … , x_n} de n objets discernables est une manière de sélectionner k fois de suite un objet dans E, sans tenir compte de l'ordre des k choix et « avec remise », le même objet pouvant donc être sélectionné plusieurs fois. On obtient ainsi un groupement non ordonné de k objets éventuellement répétés : ce groupement n’est pas un ensemble, la définition en extension d'un ensemble empêchant la répétition des éléments, mais un multiensemble. On peut formaliser cela en notant f(x_j) le nombre de fois (éventuellement nul) que l'élément x_j a été choisi, la seule contrainte étant f(x₁) + f(x₂) + … + f(x_n) = k, pour avoir un total de k objets, éventuellement répétés :

Définition — Une k-combinaison avec répétition d'un ensemble fini E de cardinal n, est une application f de E dans {0, 1, ..., k}, telle que $\sum _{x\in E}f(x)=k.$

f s'appelle aussi une combinaison avec répétition de n éléments pris k à k.

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 tout blanc 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.

Nombre de combinaisons avec répétition

Théorème — Le nombre de k-combinaisons ($k\geqslant 0$) avec répétition d'un ensemble à n éléments ($n\geqslant 1$), noté $\Gamma _{n}^{k}$ (qui se lit « Gamma n k »), ou encore $\left(\!\!{\binom {n}{k}}\!\!\right)$ est égal à $\Gamma _{n}^{k}=\left(\!\!{\binom {n}{k}}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!~(n-1)!}},$ qui est le nombre de k-combinaisons (sans répétition) de n + k – 1 éléments.

Remarque : $\Gamma _{n}^{k}$ peut aussi être vu comme le nombre de solutions de l'équation diophantienne : $x_{1}+\cdots +x_{n}=k$ où les $x_{i}$ sont des entiers naturels. $(x_{1},\cdots ,x_{n})$ est une composition faible de l'entier $k$.

Première démonstration, par double dénombrement

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 $\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 $\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 $\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 $k$, $\Gamma _{1}^{k}=1$ et pour tout entier n > 0, $\Gamma _{n}^{0}=1$.

Deuxième démonstration, par transformation en une liste de barres et d'étoiles

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 $\{a,a,b,b,b,d\}$ d'objets pris dans $\{a,b,c,d\}$ est codée par $**\,|***|\,\,|*$

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

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

Ou encore : 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 :

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

Troisième démonstration, par bijection avec les k-uplets croissants formés sur {1, 2, ..., n}.

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

Une autre représentation

À une k-combinaison avec répétition f de E, nous associons le k-uplet croissant (au sens large)

${\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 $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}.

Application

Nous venons de voir qu'il y a autant de k-combinaisons de E avec répétition que de k-uplets croissants $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 entre l'ensemble des k-uplets croissants d'éléments de E et l'ensemble des k-uplets strictement croissants $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 : $\Gamma _{n}^{k}={n+k-1 \choose k}.$

Identité mathématique

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 $k\geqslant 1$ et $n\geqslant 1$ qui donne lieu à l'identité : $\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 $\forall k\geqslant 1,n\geqslant 1$:

• L'initialisation pour $n=1$ :

$\Gamma _{1}^{k}={1+k-1 \choose k}={k \choose k}=1$

$\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 $n$, montrons qu'elle est vraie au rang $n+1$ :

$\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}$

$\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 $x=\sum _{a_{k-3}=1}^{a_{k-2}}\cdots \sum _{a_{1}=1}^{a_{2}}\sum _{a_{0}=1}^{a_{1}}1$ : $\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$

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

Quatrième démonstration

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

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

${\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 : $\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 $\Gamma _{n}^{0}=1$.

Algorithme de dénombrement

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 sans répétition ». 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.

Autres dénombrements équivalents à celui des combinaisons avec répétition

$\Gamma _{n}^{k}$ est aussi le nombre de monômes unitaires de degré k formés à partir des n indéterminées X₁, X₂, … , X_n.

C'est aussi le nombre de dérivées partielles d'ordre k d'une fonction de n variables de classe D^k, compte tenu du théorème de Schwarz qui permet de ne pas tenir compte de l'ordre dans lequel sont effectuées les dérivations (en tenant compte de l'ordre, il y en aurait n^k).

Voir aussi

Articles connexes

• Tirage (mathématiques)