Voir la source de Combinaison sans répétition

{{voir homonymes|combinaison}}
{{confusion|permutation}}

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 [[Cardinalité (mathématiques)#Cardinal d'un ensemble fini|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. 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 [[Cardinalité (mathématiques)|cardinal]] ''n'' sont les sous-ensembles de E qui ont pour taille ''k''.

Contrairement aux [[Arrangement|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 cartes|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é|probabilités]].

== Définition ==
Soit ''E'' un [[ensemble fini]] de [[Cardinalité (mathématiques)#Cardinal d'un ensemble fini|cardinal]] ''n'' et ''k'' un [[entier naturel]]. Les combinaisons de cet ensemble sont ses [[sous-ensemble]]s (ou ses parties).
{{énoncé|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<ref>[[Louis Comtet]], ''Analyse combinatoire élémentaire'', [https://books.google.fr/books?id=Mx6Va5RiENEC&pg=PA2 {{p.|2}}].</ref>{{,}}<ref>Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, ''Problèmes choisis de mathématiques supérieures'', {{p.|120}}<!--{{Google Livres|TySkMs-B_JkC}} ne montre que la couverture-->.</ref> <math>\mathcal P_k(E)</math> l’ensemble des ''k''-combinaisons de ''E''.

== Nombre de combinaisons ==
{{Voir|Coefficient binomial}}
L’ensemble <math>\mathcal P_k(E)</math> est fini et [[Ensemble fini#Cardinal d'un ensemble fini|son cardinal]] est le [[coefficient binomial]] <math>{n \choose k}</math>, aussi noté <math>C_n^k</math>. On a<ref group=note>Une démonstration est disponible sur « [https://fr.wikiversity.org/wiki/Combinatoire/Combinaisons_sans_r%C3%A9p%C3%A9tition Combinaisons sans répétition] », sur [[Wikiversité]].</ref> :
<center><math>C_n^k={n \choose k}=\frac{A_n^k}{k!}</math>,</center>
où <math>A_n^k</math> est le nombre de ''k''-[[arrangement]]s de ''E ''et ''k''! est la [[factorielle]] de ''k''.

Avec la formule pour <math>A_n^k=\frac{n!}{(n-k)!}</math>, on obtient <math>{n \choose k}=\frac{n(n-1)\ldots (n-k+1)}{k!}</math>, qui pour {{math|''k'' ≤ ''n''}} peut aussi s'écrire :
<center><math>{n \choose k}=\frac{n!}{k!(n-k)!}</math>.</center>

== Calcul du nombre de combinaisons ==
Un [[algorithme]] efficace<ref group=note>C'est par exemple celui utilisé par la [[bibliothèque logicielle|bibliothèque de programmes]] de calcul arithmétique en précision arbitraire [[GNU Multiprecision Library|GMP]], voir {{en}} [http://gmplib.org/manual/Binomial-Coefficients-Algorithm.html Binomial coefficients algorithm].</ref> pour calculer le nombre <math>\binom n k</math> de combinaisons de ''k'' éléments parmi ''n'', utilise les identités suivantes (0 ≤ ''k'' ≤ ''n'') :
<center>
<math>\binom n k = \binom n{n-k}</math>, &nbsp; &nbsp; &nbsp; &nbsp; 
<math>\binom{n+1}{k+1} = \frac{n+1}{k+1}\binom n k</math> &nbsp; &nbsp;  et &nbsp; &nbsp; 
<math>\binom n 0 = 1</math>.
</center>
La première permet de réduire le nombre d'opérations à effectuer en se ramenant à ''k'' ≤ ''n''/2. Les deux suivantes permettent de montrer que :
<center>
<math>
\binom n k = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \cdots \cdot \frac{n}{k}
</math>
</center>
À 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
:<math>
\binom{10}7=?\quad 10-7=3<7,\quad\binom 70=1\Rightarrow\binom 81=\frac 81\times1=8\Rightarrow\binom 92=\frac 92\times8=36\Rightarrow\binom{10}3=\frac{10}3\times 36=120\Rightarrow\binom{10}7=120.
</math>

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#Encadrement et approximations|coefficient binomial]]) : 

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

</math>.

== Énumération des combinaisons ==
Soient ''A'' un ensemble à ''n'' éléments, {{math|''a''}} un objet qui n'est pas dans ''A'', et ''k'' un entier naturel. Alors pour former les parties de <math>A\cup\{a\}</math> 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 :
<center>
<math>
\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\}
</math> &nbsp; &nbsp; &nbsp; &nbsp; 
(<math>\mathcal P_{k}(A)=\varnothing</math> si ''k'' > ''n'')
</center>
(cette identité a pour conséquence directe la formule de [[Suite définie par récurrence|récurrence]] permettant de construire le [[triangle de Pascal]] :
<math>
\tbinom{n+1}{k+1}=\tbinom{n}{k+1}+\tbinom nk
</math>).
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''},<br />soit{{retrait|<math>{5\choose2}={4\choose2}+{4\choose1}=6+4=10.</math>}}
:*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''},<br />soit{{retrait|<math>{5\choose3}={4\choose2}+{4\choose3}=6+4=10.</math>}}.<br />Ce sont en fait les [[Complémentaire (théorie des ensembles)|complémentaires]] des combinaisons précédentes.

<br />

== Notes et références==
=== Notes ===
{{Notes}}

=== Références === 
{{Références}}

== Voir aussi ==
{{Autres projets|v=Combinatoire/Combinaisons sans répétition|wikiversity titre=Combinaisons sans répétition}}
=== Articles connexes ===
* [[Combinaison avec répétition]]

{{Portail|mathématiques}}

[[Catégorie:Combinatoire]]
[[Catégorie:Coefficient binomial]]