Mathjax

dimanche 17 septembre 2023

Arrangements, combinaisons, coefficients binomiaux

Arrangements


 Soit $n$ un nombre entier naturel, et $k$ un entier tel que $0\leq k \leq n$. 


Soit 

$$E=\left\{x_1,x_2,\ldots,x_n \right\}$$

un ensemble de cardinal $n$.


Un arrangement de $k$ éléments de $E$ est un $k$-uplet d'éléments distincts de $E$. On le note $A_n^k$


D'après la première partie de l'article Nombres de permutations

en reprenant les mêmes notations, le nombre d'arrangements de $k$ éléments est 

$$A_n^k=p(k)=n\times (n-1) \times \ldots \times (n-(k-1)) $$


En utilisant la notation factorielle, on a donc

$$A_n^k=\frac{n\times(n-1)\times \ldots \times (n-(k-1))\times (n-k) \times \ldots \times 2 \times 1}{(n-k) \times \ldots \times 2 \times 1}=\frac{n!}{(n-k)!} $$


Combinaisons, coefficients binomiaux

Une combinaison de $k$ éléments dans un ensemble 

$$E=\left\{x_1,x_2,\ldots,x_n \right\}$$

constitué de $n$ éléments est un sous-ensemble (ou une partie) de $E$ constituée de $k$ éléments.


L'ensembles des combinaisons de $k$ éléments de $E$ est donc 

$$\mathcal C_k =\left\{ \left\{y_1,\ldots,y_k \right\}|(y_1,\ldots,y_k)\ \textrm{est un } k\textrm{-uplet de } E \right\} $$


Étant donné un sous-ensemble de $E$ de $k$ éléments, on peut former $k!$ $k$-uplets (il y a $k!$ permutations). De plus, il est impossible de former des $k$-uplets identiques à partir de sous-ensembles différents (car au moins un élément de chaque sous-ensemble n'appartient pas aux autres sous-ensembles, et n'est donc pas composantes d'un tel $k$-uplet).


On a donc 

$$\mathcal C_k=\bigcup_{(y_1,\ldots,y_k)\ k\textrm{-uplet de } E} \left\{y_1,\ldots,y_k \right\} $$


Le nombre de $k$-uplets de $E$ est donc égal au nombre de sous-ensembles de $k$ éléments de $E$ multiplié par $k!$. 

Ainsi 

$$A_n^k=k! C_n^k $$

On en déduit que $$C_n^k=\frac{A_n^k}{k!}=\frac{n!}{(n-k)!k!} $$


On appelle aussi $C_n^k$, "$k$ parmi $n$", et on utilise aussi la notation : $$\binom n k = C_n^k $$


Les nombres $C_n^k=\binom n k$ sont appelés les coefficients binomiaux. La formule du binome de Newton, qui sera l'objet d'un article futur, donne du sens à cette dénomination.


Par convention, pour tout $n$, $\binom n 0 = 1$. C'est cohérent car le seul sous-ensemble de $E$ de zéro élément est l'ensemble vide $\emptyset$.


Propriété 1. Soit $n$ et $k$ deux entiers, avec $0\leq k \leq n$. On a 

(1.1) $\binom n n =1$

(1.2) $\binom n k = \binom n {n-k}$

(1.3) $ \binom n 1 = n$


Démonstration.

(1.1) $E$ a exactement un seul sous-ensemble de $n$ éléments, $E$ lui-même.

(1.2) Pour chaque sous-ensemble a $k$ élément, il y a exactement un sous-ensemble à $n-k$ éléments, c'est le sous-ensemble de tous les éléments sauf ces $k$ éléments. 

Il y a donc autant de sous-ensembles de $E$ à $k$ éléments que de sous-ensembles de $E$ à $(n-k)$ éléments.

(1.3) $ \binom n 1$ est égal au nombre de sous-ensembles de $E$ d'un élément, il y en donc autant que d'éléments de $E$, c'est-à-dire $n$.


Triangle de Pascal 


 Propriété 2. Pour tous entiers $n,k$ tels que $0\leq k < n$

$$\binom n k + \binom n {k+1}=\binom{n+1}{k+1}$$


Preuve. On raisonne sans calcul. 

Donnons-nous un élément $x_1$ de $E$.


Il y a deux sortes de sous-ensembles de $k$ éléments de $E$ : 

  • 1) ceux qui contiennent $x_1$
  • 2) ceux qui ne contiennent pas $x_1$


1) Si un sous-ensemble de $k+1$ éléments contient $x_1$, les autres $k-1$ éléments forment un sous-ensemble de $k$ éléments. Réciproquement, pour tout sous-ensemble de $k$ éléments sauf $x_1$ (on choisit parmi $n$ éléments), on obtient un sous-ensemble de $k+1$ éléments en y ajoutant $x_1$. Il y a donc $\binom n k$ tels sous-ensembles.


2) Le nombre de sous-ensembles de $k+1$ éléments ne contenant pas $x_1$ (on choisit parmi $n$ éléments) est au nombre de $\binom{n}{k+1}$.


On en déduit que $\binom{n+1}{k+1}=\binom n k + \binom n {k+1}$.


On peut donc calculer tous les coefficients binomiaux en utilisant (1.1) et (1.2) et la propriété 2, en ne faisant que des additions. On construit pour cela le triangle de Pascal


$$\begin{array}{cccccccccc}\binom 0 0 & & & & & & & & & \\\binom 1 0  &\binom 1 1 & & & & & & & & \\\binom 2 0  &\binom 2 1 & \binom 2 2 & & & & & & & \\\binom 3 0  &\binom 3 1 & \binom 3 2 &  \binom 3 3 & & & & & & \\ \binom 4 0  &\binom 4 1 & \binom 4 2 &  \binom 4 3 &\binom 4 4 & & & & & \\\binom 5 0  &\binom 5 1 & \binom 5 2 &  \binom 5 3 &\binom 5 4 &\binom 5 5 & & & & \\\vdots &  &   &    &  &  &\ddots & & & \\\end{array}$$


Dans le triangle chaque premier élément et dernier élément de chaque ligne est un 1. Les autres éléments s'obtiennent en faisant la somme du nombre directement au dessus et de celui à la gauche de celui-ci.


$$\begin{array}{ccc}\binom n k & +  &\binom n {k+1} \\\hline &&\binom{n+1}{k+1} \\\end{array}$$


Le début du triangle de Pascal est donc ainsi :


$$\begin{array}{cccccccccc} 1 & & & & & & & & & \\ 1   &1 & & & & & & & & \\ 1  &2 & 1 & & & & & & & \\ 1  &3 & 3 &  1 & & & & & & \\ 1  &4 & 6 &   4  &1 & & & & & \\ 1 & 5  & 10 &  10 &5 &1& & & & \\\vdots &  &   &    &  &  &\ddots & & & \\\end{array}$$


Ensuite

On pourra s'intéresser à la formule du binome de Newton.

Aucun commentaire:

Enregistrer un commentaire