Cardinal des ensembles de référence

Dans cette partie, \(n\) et \(p\) désignent deux entiers naturels non nuls.

Listes

Définition

Étant donné un ensemble \(E\), une \(p\)–liste (ou \(p\)–uplet) d’éléments de \(E\) est une application de \(\left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\) dans \(E\) ; autrement dit une suite \((x_1,\dots,x_p)\) formée d’éléments (non forcément distincts) de \(E\).

Proposition

Si \(E\) est un ensemble de cardinal \(n\), il y a \(n^p\) \(p\)-listes d’éléments de \(E\).

Preuve

Par définition, l’ensemble des \(p\)-listes d’éléments de \(E\) est de même cardinal que l’ensemble \(E^p\) des suites de \(p\) éléments de \(E\). Or on sait que si \( A \) et \( B \) sont deux ensembles de cardinal fini, alors on a : \[ \mathrm{card}(A\times B) = \mathrm{card}(A) \times \mathrm{card}(B) \] Le résultat s’en déduit par récurrence (et c’est cadeau !).

Remarque

On remarquera que le résultat suivant est équivalent au précédent :

Proposition

Si \(E\) est un ensemble de cardinal \(p\) et \(F\) est un ensemble de cardinal \(n\), le nombre d’applications de \(E\) dans \(F\) est égal à \(n^p\).

Exercice

On dispose de \(6\) boules, numérotées de \(1\) à \(6\), que l’on doit disposer dans \(10\) urnes, numérotées de \(1\) à \(10\). Combien y a-t-il de dispositions possibles, sachant que chaque urne a une contenance illimitée ?

Solution

Disposer les \(6\) boules discernables dans les \(10\) urnes discernables revient à construire une \(6\)-liste d’éléments de \(\left[\kern-0.15em\left[ {1,10} \right]\kern-0.15em\right]\) (le \(k^{\grave{e}me}\) élément de la liste indiquant dans quelle urne sera placée la boule numéro \(k\)), donc il y a \(10^6\) dispositions possibles.

Listes d’éléments distincts

Définition

Étant donné un ensemble \(E\), un arrangement de \(p\) éléments de \(E\) est une \(p\)-liste d’éléments distincts de \(E\) ; autrement dit une suite \((x_1,\dots,x_p)\) formée d’éléments distincts de \(E\), ou encore une application injective de \(\left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\) dans \(E\).

Proposition

Si \(E\) est un ensemble de cardinal \(n\), le nombre d’arrangements de \(p\) éléments de \(E\) est : \[\begin{cases} \displaystyle\frac{n!}{(n-p)!}=n(n-1)\cdots(n-p+1) &\text{si } p\leqslant n \rule[0pt]{0pt}{20pt}\\ \hfill 0 \hfill &\text{sinon} \end{cases}\]

Remarque

Ce nombre est parfois noté \(A_n^p\) (notation hors programme).

Exercice

Démontrer la proposition. On pourra procéder par récurrence sur \(p\).

Solution

On note \(E=\{x_1,\dots,x_n\}\).

Le cas \(p>n\) est immédiat car il n’est alors pas possible de choisir \(p\) éléments distincts de \(E\). Montrons alors par récurrence que, pour tout \(p\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), la proposition \(\mathscr H(p)\) : le nombre d’arrangements de \(p\) éléments de \(E\) est \(\dfrac{n!}{(n-p)!}\) est vraie.

Pour \(p=1\), il y a \(n\) \(1\)-listes d’éléments distincts de \(E\) (on choisit un unique élément de \(E\)) et on remarque que : \[n=\frac{n!}{(n-1)!}\] donc \(\mathscr H(1)\) est vraie.
Soit \(p\in\left[\kern-0.15em\left[ {1,n-1} \right]\kern-0.15em\right]\). On suppose que \(\mathscr H(p)\) est vraie. Construire une \((p+1)\)-liste \((a_1,\dots,a_{p+1})\) d’éléments distincts de \(E\) équivaut alors à :
- construire la \(p\)-liste des \(p\) premiers éléments \((a_1,\dots,a_p)\) distincts de \(E\) : \(\dfrac{n!}{(n-p)!}\) façons d’après \(\mathscr H(p)\), puis :
- choisir l’élément \(a_{p+1}\), distinct de \(a_1,\dots,a_p\) : \(n-p\) façons.
Ainsi, le nombre de \((p+1)\)-listes d’éléments distincts de \(E\) est égal à : \begin{align*}\frac{n!}{(n-p)!}\times (n-p) &=\frac{n!}{(n-p-1)!} \\ &=\frac{n!}{(n-(p+1))!}\end{align*} donc : \(\mathscr H(p)\Rightarrow \mathscr H(p+1)\).
Finalement, \(\mathscr H(p)\) est vraie pour tout \(p\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\).

Remarque

On remarquera que le résultat suivant est équivalent au précédent :

Proposition

Si \(E\) est un ensemble de cardinal \(p\) et \(F\) est un ensemble de cardinal \(n\), le nombre d’applications injectives de \(E\) dans \(F\) est : \[\begin{cases} \displaystyle\frac{n!}{(n-p)!}=n(n-1)\cdots(n-p+1) &\text{si } p\leqslant n \rule[0pt]{0pt}{20pt}\\ \hfill 0 \hfill &\text{sinon} \end{cases}\]

Exercice

Solution

Si chaque urne ne peut contenir plus d’une boule, disposer les \(6\) boules discernables dans les \(10\) urnes discernables revient à construire une \(6\)-liste d’éléments distincts de \(\left[\kern-0.15em\left[ {1,10} \right]\kern-0.15em\right]\) (le \(k^{\grave{e}me}\) élément de la liste indiquant dans quelle urne sera placée la boule numéro \(k\)), donc il y a \[\dfrac{10!}{(10-6)!}=10\times 9 \times 8\times 7\times 6 \times 5\] dispositions possibles.

Permutations

Définition

Étant donné un ensemble \(E\) de cardinal \(n\), une permutation de \(E\) est une \(n\)-listes d’éléments distincts de \(E\) ; autrement dit un arrangement de \(n\) éléments de \(E\), ou encore une application bijective de \(E\) sur \(E\).

Proposition

Si \(E\) est un ensemble de cardinal \(n\), le nombre de permutations de \(E\) est \(n!\)

Exercice

On dispose de \(6\) boules, numérotées de \(1\) à \(6\), que l’on doit disposer dans \(6\) urnes, numérotées de \(1\) à \(6\), de telle sorte qu’aucune urne ne soit vide. Combien y a-t-il de dispositions possibles ?

Solution

Comme aucune urne ne doit être vide et comme il y a autant d’urnes que de boules, disposer les boules revient à construire une permutation de l’ensemble des \(6\) boules, donc il y a \(6!\) dispositions possibles.

Combinaisons

Définition

Étant donné un ensemble \(E\) de cardinal \(n\), une combinaison de \(p\) éléments de \(E\) est une partie de \(E\), de cardinal \(p\) ; autrement dit un sous-ensemble \(\{x_1,\dots,x_p\}\) formé de \(p\) éléments distincts de \(E\).

Proposition – Nombre de combinaisons

Si \(E\) est un ensemble de cardinal \(n\), le nombre de combinaisons de \(p\) éléments de \(E\) est : \[\binom np=\begin{cases} \displaystyle\frac{n!}{p!\,(n-p)!} &\text{si } p\leqslant n \rule[0pt]{0pt}{20pt}\\ \hfill 0 \hfill &\text{sinon} \rule[0pt]{0pt}{15pt} \end{cases}\] Ce résultat est encore vrai si \(p=0\).

Remarque

Les nombres \(\displaystyle\binom np\) sont appelés coefficients binomiaux, car ils interviennent en particulier dans la formule du binôme de Newton.

Preuve

On note \(\binom np\) le nombre de combinaisons de \(p\) éléments de \(E\). Le résultat est immédiat si \(p>n\). On suppose maintenant que \(1\leqslant p \leqslant n\). On remarque alors que construire un arrangement de \(p\) éléments de \(E\) équivaut à choisir une combinaison \(\{a_1,\dots,x_p\}\) de \(p\) éléments de \(E\) puis à construire une permutation de \(\{x_1,\dots,x_p\}\) ; comme il y a \(\binom np\) combinaisons de \(p\) éléments de \(E\) et, pour chacune de ces combinaisons, il y a \(p!\) permutations possibles, on a donc : \[A_n^p=\binom np\times p!\] ce qui prouve le résultat si \(1\leqslant p \leqslant n\). Le cas \(p=0\) est immédiat car \(\varnothing\) est l’unique combinaison de \(0\) éléments de \(E\).

Exercice

Si \(n\) et \(p\) sont deux entiers naturels tels que : \(1\leqslant p\leqslant n\), déterminer le nombre de suites \((x_i)_{1\leqslant i\leqslant p}\) d’éléments de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), strictement croissantes.

Solution

Comme on cherche des suites strictement croissantes d’entiers, on peut remarquer qu’il est équivalent de construire une suite de \(p\) éléments de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), strictement croissante, et de choisir une partie de \(p\) éléments distincts de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) puis de ranger ces éléments dans l’ordre croissant. Il y a donc \(\binom np\) suites strictement croissantes de \(p\) éléments de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\).

Proposition

Si \(n\) et \(p\) sont deux entiers naturels quelconques, alors :

Si \(0\leqslant p\leqslant n\) : \(\displaystyle\binom np=\binom n{n-p}\)
Si \(n\geqslant 1\) et \(p\geqslant 1\), alors : \(\displaystyle\binom np=\frac{n}{p}\binom {n-1}{p-1}\)
\(\displaystyle\sum_{p=0}^n \binom np=\binom n0+\binom n1+\cdots +\binom nn=2^n\)

Remarque

Comme il y a souvent des doutes sur la deuxième formule, il est important de savoir la retrouver rapidement.

Exercice

Démontrer la proposition.

Solution

Par définition, si \(0\leqslant p \leqslant n\), on a : \begin{align*}\binom np=\frac{n!}{p!\,(n-p)!}&=\frac{n!}{(n-(n-p))!\,(n-p)!} \\&=\binom n{n-p}\end{align*}
Par définition, on a, si \(n\geqslant 1\) et \(p\geqslant 1\) : \begin{align*}\binom np &=\frac{n!}{p!\,(n-p)!} \\&=\frac{n}{p}\times \frac{(n-1)!}{(p-1)!\,((n-1)-(p-1))!} \\&=\frac{n}{p}\,\binom{n-1}{p-1}\end{align*}
D’après la formule du binôme de Newton, on a : \begin{align*} \sum_{k=0}^n \binom nk &=\sum_{k=0}^n \binom nk \times 1^k \times 1^{n-k} \\ &=(1+1)^n \\ &=2^n\end{align*}

Proposition

Formule du triangle de Pascal Si \(n\) et \(p\) sont deux entiers naturels quelconques, alors : \[\binom{n+1}{p+1}=\binom{n}{p+1}+\binom np\]

Exercice

Démontrer la formule du triangle de Pascal.

Solution

Par définition, on a, si \(0\leqslant p\leqslant p+1\leqslant n\) : \[\begin{aligned} \binom n{p+1}+\binom np &= \frac{n!}{(p+1)!\,(n-p-1)!}+\frac{n!}{p!\,(n-p)!}\\ &=\frac{n!\,[(n-p)+(p+1)]}{(p+1)!\,(n-p)!}\\ &= \frac{(n+1)!}{(p+1)!\,((n+1)-(p+1))!}\\ &=\binom{n+1}{p+1} \end{aligned}\]

De plus, si \(p>n\), on a : \[\binom n{p+1}=\binom np=\binom {n+1}{p+1}=0\]

donc on a encore : \[\binom n{p+1}+\binom np = \binom{n+1}{p+1}\]

Enfin, si \(n=p\), on a : \[\binom n{p+1}=0 \quad\text{et}\quad\binom np=\binom {n+1}{p+1}=1\]

donc on a encore une fois : \[\binom n{p+1}+\binom np = \binom{n+1}{p+1}\]

Remarque

Intuitivement, on peut aussi se souvenir que construire une partie de \(p+1\) éléments de \(\left[\kern-0.15em\left[ {1,n+1} \right]\kern-0.15em\right]\), deux cas disjoints sont possibles :

soit on ne prend pas l’élément \(n+1\), et il reste alors à choisir une partie de \(p+1\) éléments de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) : \(\binom n{p+1}\) choix,
soit on prend l’élément \(n+1\), et il reste alors à choisir une partie de \(p\) éléments de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) : \(\binom np\) choix.

Proposition

Si \(E\) est un ensemble de cardinal \(n\), alors : \[\mathrm{Card}\,(\mathscr P(E))=2^{\mathrm{Card}\,(E)}=2^n\]

Preuve

Si on note, pour tout \(k\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\), \(P_k\) l’ensemble des parties de \(E\) qui sont de cardinal \(k\), on remarque que \(\{P_k,k\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\}\) est une partition de \(\mathscr P(E)\) et donc : \[\mathrm{Card}(\mathscr P(E))=\sum_{k=0}^n \mathrm{Card}(P_k)\] et ainsi : \[\mathrm{Card}(\mathscr P(E))=\sum_{k=0}^n \binom nk=2^n\]