Combinaisons d'un ensemble fini

Définition : Soient $n$ et $k$ deux entiers naturels tels que $0 \leq k \leq n$, et $E$ un ensemble fini de cardinal $n$. On appelle combinaison de $k$ éléments de $E$ toute partie de $E$ ayant $k$ éléments.

Le nombre de combinaisons de $k$ éléments de $E$ est noté $\begin{pmatrix}n\\k\end{pmatrix}$ ou $C_n^k$ .

Remarque : Les nombres $\begin{pmatrix}n\\k\end{pmatrix}$ sont également appelés coefficients binomiaux et se lisent « $k$ parmi $n$ ».

Exemple :
Soit $A = \lbrace 1 ; 2 ; 3 \rbrace$.
$\circ\quad$ Les parties de $A$ sont : $\emptyset$, $\lbrace 1 \rbrace$, $\lbrace 2 \rbrace$, $\lbrace 3 \rbrace$, $\lbrace 1 ; 2 \rbrace$, $\lbrace 1 ; 3 \rbrace$, $\lbrace 2 ; 3 \rbrace$, $\lbrace 1 ; 2 ; 3 \rbrace$.
$\circ\quad$ Il y a 3 parties à 1 élément, $\begin{pmatrix}3\\1\end{pmatrix}=3$
$\circ\quad$ Mais il y a autant de parties à 1 élément que de parties à 2 éléments (les complémentaires) dans cet ensemble, donc : $\begin{pmatrix}3\\2\end{pmatrix} = 3$.

Propriété :
Soient $n$ et $k$ deux entiers naturels tels que $k \leq n$, alors :
$C_n^k=\begin{pmatrix}n\\k\end{pmatrix} = \dfrac{n!}{k!(n-k)!}$.

$\circ\quad$Symétrie : $\begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n\\n-k\end{pmatrix}$.

$\circ\quad$Exemples particuliers :
$\circ\quad$ si $k=0$ , $\begin{pmatrix}n\\0\end{pmatrix} = 1$: Il n’y a qu’une seule façon de ne rien choisir : le sous-ensemble vide $\varnothing$.
$\circ\quad$ si $k=1$ , $\begin{pmatrix}n\\1\end{pmatrix} = n$ : Choisir un élément parmi $n$ donne $n$ sous-ensembles à 1 élément.
$\circ\quad$ si $k=2$ , $\begin{pmatrix}n\\2\end{pmatrix} = \dfrac{n(n-1)}{2}$ : Pour choisir 2 éléments sans ordre parmi $n$, on a $\dfrac{n(n-1)}{2}$ possibilités.

$\circ\quad$ $(n+1)!=n!\times (n+1)$ est une relation intéressante (simplification de fractions etc.) dont on peut donner un exemple $7!=6!\times 7$