Formulaire de Mathématiques : combinaisons
Définition et calcul
Définition :
$E$ étant un ensemble à $n$ éléments, on appelle combinaison de $p$ éléments de $E$ toute collection non ordonnée de $p$ éléments distincts de $E$, ie toute partie de $E$ à $p$ éléments.
On note $\binom n p$ le nombre de combinaison de p éléments parmi n. On a :
$$\binom np=\frac{n!}{p!(n-p)!}=\frac{n(n-1)\dots(n-p+1)}{p(p-1)\dots 1}.$$
Ex : Tirage par poignées.Une urne contient n boules numérotée de 1 à n. On tire simultanément p boules de U. Le nombre de tirages possibles vaut le nombre de combinaisons de p éléments parmi n.
Propriétés
- Symétrie : $\binom np=\binom n{n-p}$, valable pour $0\leq p\leq n$.
- $\binom n0=\binom nn=1$, valable pour tout $n\geq 0$.
- $\binom n1=\binom n{n-1}=n$, valable pour tout $n\geq 1$.
- Formule de Pascal : $$\binom np=\binom {n-1}p+\binom {n-1}{p-1}.$$ Les 4 propriétés précédentes permettent de calculer de proche en proche tous les coefficients binomiaux.
- Formule du binôme : $$(x+y)^n=\sum_{k=0}^n \binom nk x^ky^{n-k}.$$
- Formule de Vandermonde : $$\sum_{k=0}^n \binom ak\binom b{n-k}=\binom {a+b}n.$$