Combinatoire et dénombrement

Les ensembles $A$ et $\overline{A}$ sont disjoints (un élément de $E$ ne peut pas être à la fois dans $A$ et hors de $A$) et leur réunion est $E$.

D'après le principe additif : $\mathrm{card}(E)=\mathrm{card}(A)+\mathrm{card}(\overline{A})$, d'où $\mathrm{card}(\overline{A})=\mathrm{card}(E)-\mathrm{card}(A)$.

On note $n=\mathrm{card}(E)$, $p=\mathrm{card}(F)$ et $E=\{a_1;\ldots;a_n\}$.

Pour chaque $i$, l'ensemble $\{a_i\}\times F$ des couples de première composante $a_i$ contient exactement $p$ éléments : $(a_i;y)$ pour $y\in F$.

Ces $n$ ensembles sont deux à deux disjoints (deux couples de premières composantes différentes sont différents) et leur réunion est $E\times F$.

D'après le principe additif : $$\mathrm{card}(E\times F)=\underbrace{p+p+\cdots+p}_{n\text{ termes}}=n\times p.$$

Pour $k\geqslant 1$, on note $\mathcal{P}(k)$ : « $\mathrm{card}(E^k)=n^k$ ».

Initialisation. $E^1$ est l'ensemble des 1-uplets $(x_1)$ avec $x_1\in E$ : il y en a $n=n^1$. $\mathcal{P}(1)$ est vraie.

Hérédité. Soit $k\geqslant 1$ tel que $\mathcal{P}(k)$ est vraie. Un $(k+1)$-uplet $(x_1;\ldots;x_k;x_{k+1})$ s'identifie au couple formé du k-uplet $(x_1;\ldots;x_k)\in E^k$ et de l'élément $x_{k+1}\in E$. Donc $E^{k+1}$ s'identifie à $E^k\times E$ et, par le principe multiplicatif et l'hypothèse de récurrence : $$\mathrm{card}(E^{k+1})=\mathrm{card}(E^k)\times\mathrm{card}(E)=n^k\times n=n^{k+1}.$$ $\mathcal{P}(k+1)$ est vraie.

Conclusion. Pour tout $k\geqslant 1$, $\mathrm{card}(E^k)=n^k$.

On note $A_k$ le nombre de k-uplets d'éléments distincts de $E$, pour $1\leqslant k\leqslant n$. Montrons par récurrence finie que $A_k=n(n-1)\cdots(n-k+1)$.

Initialisation. Pour $k=1$, un 1-uplet $(x_1)$ est toujours à éléments distincts : $A_1=n$.

Hérédité. Soit $k$ avec $1\leqslant k\leqslant n-1$ et $A_k=n(n-1)\cdots(n-k+1)$. Un $(k+1)$-uplet d'éléments distincts s'obtient de façon unique en choisissant d'abord un k-uplet d'éléments distincts $(x_1;\ldots;x_k)$, puis un élément $x_{k+1}$ différent de $x_1,\ldots,x_k$. Quel que soit le k-uplet choisi, il reste exactement $n-k$ choix pour $x_{k+1}$. Par le principe multiplicatif : $$A_{k+1}=A_k\times(n-k)=n(n-1)\cdots(n-k+1)(n-k).$$ C'est la formule au rang $k+1$.

Écriture avec les factorielles. $$n(n-1)\cdots(n-k+1)=\frac{n(n-1)\cdots(n-k+1)\times(n-k)\times\cdots\times1}{(n-k)\times\cdots\times1}=\frac{n!}{(n-k)!}.$$ Pour $k=n$, le dénominateur vaut $0!=1$, ce qui justifie la convention.

Pour $k=0$ : la seule partie à 0 élément est $\emptyset$, donc $\binom{n}{0}=1$, et $\frac{n!}{0!\,n!}=1$. La formule est vraie.

Soit $1\leqslant k\leqslant n$. On dénombre de deux façons l'ensemble $\mathcal{A}$ des k-uplets d'éléments distincts de $E$.

• D'après la section précédente, $\mathrm{card}(\mathcal{A})=\dfrac{n!}{(n-k)!}$.
• Autre façon : construire un tel k-uplet revient à choisir d'abord l'ensemble $\{x_1;\ldots;x_k\}$ de ses composantes, partie de $E$ à $k$ éléments ($\binom{n}{k}$ choix), puis l'ordre de ces $k$ éléments, c'est-à-dire une permutation de cette partie ($k!$ choix, quelle que soit la partie). Chaque k-uplet d'éléments distincts est obtenu une et une seule fois. Par le principe multiplicatif, $\mathrm{card}(\mathcal{A})=\binom{n}{k}\times k!$.

On en déduit $\binom{n}{k}\times k!=\dfrac{n!}{(n-k)!}$, d'où $$\binom{n}{k}=\frac{n!}{k!\,(n-k)!}.$$ La seconde écriture vient de $\dfrac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$.

Par dénombrement. Soit $E$ un ensemble à $n$ éléments. À toute partie $A$ de $E$ à $k$ éléments, on associe son complémentaire $\overline{A}$, qui possède $n-k$ éléments. Cette correspondance est une bijection entre les parties à $k$ éléments et les parties à $n-k$ éléments : toute partie $B$ à $n-k$ éléments est le complémentaire d'une unique partie à $k$ éléments, à savoir $\overline{B}$. Les deux ensembles de parties ont donc le même nombre d'éléments : $\binom{n}{k}=\binom{n}{n-k}$.

Par le calcul. $$\binom{n}{n-k}=\frac{n!}{(n-k)!\,(n-(n-k))!}=\frac{n!}{(n-k)!\,k!}=\binom{n}{k}.$$

Interprétation : choisir les $k$ éléments que l'on garde revient à choisir les $n-k$ éléments que l'on écarte.

Soit $E$ un ensemble à $n$ éléments ($n\geqslant 2$) et $a$ un élément fixé de $E$. On note $E'=E\setminus\{a\}$, qui a $n-1$ éléments.

Les parties de $E$ à $k$ éléments se répartissent en deux catégories disjointes.

• Celles qui contiennent $a$. Une telle partie s'écrit $\{a\}\cup B$ où $B$ est une partie de $E'$ à $k-1$ éléments, et ce $B$ est unique. Il y en a donc $\binom{n-1}{k-1}$.
• Celles qui ne contiennent pas $a$. Ce sont exactement les parties de $E'$ à $k$ éléments. Il y en a $\binom{n-1}{k}$.

Par le principe additif : $$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.$$

Soit $1\leqslant k\leqslant n-1$. On a $$\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{(n-1)!}{(k-1)!\,(n-k)!}+\frac{(n-1)!}{k!\,(n-1-k)!}.$$ On réduit au même dénominateur $k!\,(n-k)!$, en utilisant $k!=k\times(k-1)!$ et $(n-k)!=(n-k)\times(n-k-1)!$ : $$\begin{aligned}\binom{n-1}{k-1}+\binom{n-1}{k}&=\frac{k\,(n-1)!}{k!\,(n-k)!}+\frac{(n-k)\,(n-1)!}{k!\,(n-k)!}\\&=\frac{(n-1)!\,\big(k+(n-k)\big)}{k!\,(n-k)!}\\&=\frac{n\,(n-1)!}{k!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}=\binom{n}{k}.\end{aligned}$$

Si $n=0$, $E=\emptyset$ a une seule partie, $\emptyset$, et $2^0=1$.

Soit $n\geqslant1$ et $E=\{x_1;x_2;\ldots;x_n\}$. À toute partie $A$ de $E$, on associe le $n$-uplet $(\varepsilon_1;\ldots;\varepsilon_n)\in\{0;1\}^n$ défini par $$\varepsilon_i=\begin{cases}1 & \text{si } x_i\in A\\ 0 & \text{si } x_i\notin A.\end{cases}$$ Réciproquement, tout $n$-uplet de $\{0;1\}^n$ définit une unique partie de $E$ : celle formée des $x_i$ pour lesquels $\varepsilon_i=1$.

Cette correspondance est donc une bijection entre $\mathcal{P}(E)$ et $\{0;1\}^n$. Ces deux ensembles ont le même cardinal, et d'après le nombre de k-uplets : $$\mathrm{card}\big(\mathcal{P}(E)\big)=\mathrm{card}\big(\{0;1\}^n\big)=2^n.$$ Autrement dit : pour construire une partie, on décide, pour chacun des $n$ éléments, s'il est dedans ou non, soit 2 choix à chaque fois.

Soit $E$ un ensemble à $n$ éléments. Pour $0\leqslant k\leqslant n$, on note $\mathcal{P}_k$ l'ensemble des parties de $E$ à $k$ éléments ; $\mathrm{card}(\mathcal{P}_k)=\binom{n}{k}$.

Toute partie de $E$ a un nombre d'éléments compris entre $0$ et $n$, et un seul : les ensembles $\mathcal{P}_0,\ldots,\mathcal{P}_n$ sont deux à deux disjoints et leur réunion est $\mathcal{P}(E)$. Par le principe additif : $$\sum_{k=0}^{n}\binom{n}{k}=\mathrm{card}\big(\mathcal{P}(E)\big)=2^n.$$