Combinaison (mathématiques)
En mathématiques, lorsqu'on choisit k objets parmi n objets discernables (numérotés de 1 à n)
et que l’ordre dans lequel les objets sont placés (ou énumérés) n’a pas d’importance, on peut
les représenter par un ensemble à k éléments. Les combinaisons servent donc, entre autres, en
combinatoire. Un exemple est la main qu'on obtient en tirant simultanément k cartes dans un
jeu de n cartes ; ou au jeu du loto, le tirage final (qui ne dépend pas de l’ordre d’apparition des
boules obtenues).

Définition mathématique
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 note1,2 l’ensemble des k-combinaisons de E. L’ensemble est fini et son


cardinal est le coefficient binomial (lu « k parmi n » ), encore noté parfois (lu
« combinaison de k parmi n »), la première notation étant préconisée par la norme ISO 31-11.


On a , où est le nombre de k-arrangements de E et k! est la factorielle de k.

[afficher]
Démonstration



Avec la formule pour , on obtient , qui pour k ≤ n


peut aussi s'écrire : .

Calcul du nombre de combinaisons
Un algorithme efficace3 pour calculer le nombre de combinaisons de k éléments parmi n,
utilise les identités suivantes (0 ≤ k ≤ n) :



, et

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 :
À 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




É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 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 :

( si k
> n)

(cette identité a pour conséquence directe la formule de récurrence permettant de construire le
triangle de Pascal : ). 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 :
o celles qui contiennent deux éléments distincts de a : {b, c}, {b, d}, {b, e}, {c,
d}, {c, e}, {d, e}
o celles qui contiennent a et un autre élément : {a, b}, {a, c}, {a, d}, {a, e},



soit

 Les combinaisons de 3 éléments choisis parmi les 5 éléments de A sont :
o 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}
o celles qui contiennent trois éléments distincts de a : {b, c, d}, {b, c, e}, {b, d,
e}, {c, d, e}
 soit .
Ce sont en fait les complémentaires des combinaisons précédentes.


Formule du binôme de Newton
La formule de Newton est une formule mathématique donnée par Isaac Newton1 pour trouver
le développement d'une puissance entière quelconque d'un binôme. Elle est aussi appelée
formule du binôme de Newton, ou plus simplement formule du binôme.

Énoncé
Soient x et y deux éléments d'un anneau (par exemple deux nombres réels ou complexes, deux
polynômes, deux matrices carrées de même taille, etc.) qui commutent (c'est-à-dire tels que xy
= yx — par exemple pour des matrices : y = la matrice identité) et un entier naturel n, alors




où les nombres (parfois aussi notés ) sont les coefficients
0
binomiaux, « ! » désignant la factorielle et x l'élément unité de l'anneau.

En remplaçant dans la formule y par –y, on obtient :




Exemples :




Démonstration par récurrence
Pour n = 0 on a bien :



.

Pour n entier supérieur ou égal à 1, démontrons la formule de l'énoncé par récurrence.
Initialisation

Pour n = 1 on a bien :



.

Caractère héréditaire

Soit n un entier supérieur ou égal à 1, montrons que si la relation est vraie pour n, elle l'est
aussi pour n+1 :

Par hypothèse de récurrence :




Par distributivité de la multiplication par rapport à l'addition :




Par factorisation :




En utilisant la formule du triangle de Pascal :




ce qui termine la démonstration2.

Variante de la démonstration


Une preuve beaucoup plus intuitive3 utilise le fait que le coefficient binomial est le
nombre de parties à k éléments dans un ensemble à n éléments. Quand on développe
l'expression
on obtient une somme de monômes de la forme xjyk où j et k représentent respectivement le
nombre de fois qu'on a choisi x ou y en développant. On a forcément j = n – k, puisqu'à


chaque fois qu'on ne choisit pas y, on choisit x. Enfin, comme il y a manières différentes
de choisir k fois la valeur y parmi les n expressions (x + y) multipliées ci-dessus, le monôme


xn–kyk doit apparaître dans le développement avec le coefficient .

Généralisations
La démonstration par récurrence peut être calquée pour démontrer la formule de Leibniz pour
la dérivée n-ième d'un produit (inversement, la formule du binôme peut se déduire de celle de
Leibniz appliquée au produit exp(ax)exp(bx))[réf. nécessaire].

La méthode combinatoire de sa variante permet de généraliser l'identité polynomiale




en




où les σk désignent les polynômes symétriques élémentaires.

Il est également possible de généraliser la formule à des sommes de plus de deux termes (voir
l'article Formule du multinôme de Newton) et à des exposants non entiers (voir l'article
Formule du binôme généralisée) ou entiers négatifs (voir l'article Formule du binôme négatif).