Combinaisons d'un ensemble fini

Signaler

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

Le nombre de combinaisons de kk éléments de EE est noté (nk)\begin{pmatrix}n\\k\end{pmatrix} ou CnkC_n^k .

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

Exemple :
Soit A={1;2;3}A = \lbrace 1 ; 2 ; 3 \rbrace.
\circ\quad Les parties de AA sont : \emptyset, {1}\lbrace 1 \rbrace, {2}\lbrace 2 \rbrace, {3}\lbrace 3 \rbrace, {1;2}\lbrace 1 ; 2 \rbrace, {1;3}\lbrace 1 ; 3 \rbrace, {2;3}\lbrace 2 ; 3 \rbrace, {1;2;3}\lbrace 1 ; 2 ; 3 \rbrace.
\circ\quad Il y a 3 parties à 1 élément, (31)=3\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 : (32)=3\begin{pmatrix}3\\2\end{pmatrix} = 3.

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

\circ\quadSymétrie : (nk)=(nnk)\begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n\\n-k\end{pmatrix}.

\circ\quadExemples particuliers :
\circ\quad si k=0k=0 , (n0)=1\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=1k=1 , (n1)=n\begin{pmatrix}n\\1\end{pmatrix} = n : Choisir un élément parmi nn donne nn sous-ensembles à 1 élément.
\circ\quad si k=2k=2 , (n2)=n(n1)2\begin{pmatrix}n\\2\end{pmatrix} = \dfrac{n(n-1)}{2} : Pour choisir 2 éléments sans ordre parmi nn, on a n(n1)2\dfrac{n(n-1)}{2} possibilités.

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