Dénombrement

1Ensembles finis et cardinal

Définition. Un ensemble $E$ est fini s’il est vide, ou s’il existe $n\in\N^{*}$ et une bijection de $\intent{1}{n}$ sur $E$. Cet entier $n$ est alors unique : on l’appelle le cardinal de $E$ et on le note $\Card E$ ou $\abs{E}$, avec la convention $\Card\emptyset=0$. Un ensemble qui n’est pas fini est dit infini.

Remarque. Tout fondement théorique des notions d’entier naturel et de cardinal est hors programme : l’unicité de $n$ ci-dessus, ainsi que les propriétés les plus intuitives de ce chapitre, sont admises. Ce qui est en revanche exigible, c’est de savoir compter : reconnaître l’objet que l’on dénombre, choisir le bon modèle, et rédiger le comptage.

Propriété — parties d’un ensemble fini. Soit $E$ un ensemble fini et $A\subset E$. Alors $A$ est fini et

Réciproquement, si $E$ est infini, $E$ possède des parties finies de cardinal arbitrairement grand.

Théorème — cas d’égalité des cardinaux. Soient $E$ et $F$ deux ensembles finis de même cardinal et $f:E\to F$. Alors

2Opérations sur les cardinaux

Théorème — principe d’addition. Si $A$ et $B$ sont deux ensembles finis disjoints ($A\cap B=\emptyset$), alors $A\cup B$ est fini et $\Card(A\cup B)=\Card A+\Card B$. Plus généralement, si $E$ est fini et si $(A_{1},\dots,A_{p})$ est une partition de $E$ (parties non vides, deux à deux disjointes, de réunion $E$), alors

Propriété — complémentaire et différence. Soient $E$ fini et $A,B\subset E$. Alors

Théorème — cardinal d’une réunion quelconque. Pour $A$ et $B$ finis,

Idée de preuve (exigible). $A\cup B$ est la réunion disjointe de $A$ et de $B\setminus A$, donc $\Card(A\cup B)=\Card A+\Card(B\setminus A)=\Card A+\Card B-\Card(A\cap B)$ par la propriété précédente.

Théorème — principe multiplicatif. Si $A_{1},\dots,A_{p}$ sont finis, alors $A_{1}\times\cdots\times A_{p}$ est fini et

Méthode — dénombrer par choix successifs. si un objet se construit par $p$ choix successifs, le $i$-ième offrant $n_{i}$ possibilités quelles que soient les réponses aux précédents, et si deux suites de choix distinctes donnent des objets distincts, alors il y a $n_{1}n_{2}\cdots n_{p}$ objets. C’est le principe multiplicatif ; la clause « quelles que soient les réponses aux précédents » est celle que l’on oublie.

3Applications, parties, listes

Notation. Pour $E$ et $F$ deux ensembles, $\mathcal{F}\left(E,F\right)$ (noté aussi $F^{E}$) désigne l’ensemble des applications de $E$ dans $F$. Une $p$-liste (ou $p$-uplet) d’éléments de $E$ est un élément de $E^{p}$ ; c’est la même chose qu’une application de $\intent{1}{p}$ dans $E$.

Théorème — nombre d’applications. Soient $E$ et $F$ finis, $\Card E=p$ et $\Card F=n$. Alors

En particulier, le nombre de $p$-listes d’éléments d’un ensemble à $n$ éléments est $n^{p}$.

Idée de preuve (exigible). En notant $E=\ens{x_{1},\dots,x_{p}}$, l’application $f\mapsto\left(f(x_{1}),\dots,f(x_{p})\right)$ permet d’identifier $\mathcal{F}\left(E,F\right)$ et $F^{p}$ : se donner $f$, c’est se donner indépendamment les $p$ images, soit $n$ choix pour chacune. On conclut par le principe multiplicatif. (On peut aussi raisonner par récurrence sur $p$.)

Théorème — nombre de parties. Si $E$ est fini de cardinal $n$, alors $\mathcal{P}(E)$ est fini et

Idée de preuve (exigible). L’application $A\mapsto\mathbf{1}_{A}$ est une bijection de $\mathcal{P}(E)$ sur $\mathcal{F}\left(E,\ens{0\,;1}\right)$ (chapitre 2), ensemble de cardinal $2^{n}$ par le théorème précédent. Autrement dit : choisir une partie, c’est décider pour chacun des $n$ éléments s’il y appartient ou non, soit $2$ choix indépendants répétés $n$ fois.

4Listes d’éléments distincts, injections, permutations

Définition. Une $p$-liste d’éléments distincts de $E$ (on dit aussi un arrangement de $p$ éléments de $E$) est un $p$-uplet $\left(x_{1},\dots,x_{p}\right)\in E^{p}$ dont les composantes sont deux à deux distinctes.

Théorème. Soit $E$ fini de cardinal $n$ et $p\in\N$. Le nombre de $p$-listes d’éléments distincts de $E$ vaut

C’est aussi le nombre d’applications injectives d’un ensemble de cardinal $p$ dans un ensemble de cardinal $n$.

Idée de preuve (exigible). On construit la liste par choix successifs : $n$ possibilités pour $x_{1}$, puis $n-1$ pour $x_{2}$ (toutes sauf $x_{1}$), …, puis $n-p+1$ pour $x_{p}$ — et ce nombre de possibilités à la $i$-ième étape ne dépend pas des choix précédents, seulement de leur nombre. Si $p>n$, il n’existe aucune injection d’un ensemble de cardinal $p$ dans un ensemble de cardinal $n$ (sinon $p=\Card f(E)\leq n$).

Propriété — permutations. Une permutation de $E$ est une bijection de $E$ sur $E$. Si $\Card E=n$, le nombre de permutations de $E$ est $\boxed{n!}$ (cas $p=n$ ci-dessus : une $n$-liste d’éléments distincts de $E$ énumère $E$ tout entier). On retrouve $\Card\mathfrak{S}_{n}=n!$ du chapitre 19.

Remarque. Le nombre d’arrangements est parfois noté $A_{n}^{p}$ ; cette notation ne figure pas au programme et il est préférable d’écrire $\frac{n!}{(n-p)!}$.

5Combinaisons et coefficients binomiaux

Définition. Soit $E$ fini de cardinal $n$ et $p\in\N$. Une $p$-combinaison de $E$ est une partie de $E$ à $p$ éléments. On note $\mathcal{P}_{p}(E)=\ens{A\in\mathcal{P}(E),\ \Card A=p}$.

Théorème — le résultat central du chapitre. Pour $E$ fini de cardinal $n$ et $p\in\N$,

c’est-à-dire $\frac{n!}{p!\,(n-p)!}$ si $0\leq p\leq n$, et $0$ si $p>n$.

Idée de preuve (exigible) : on compte les $p$-listes d’éléments distincts de deux façons. Supposons $0\leq p\leq n$ et notons $N=\Card\mathcal{P}_{p}(E)$. Construire une $p$-liste d’éléments distincts, c’est choisir l’ensemble $A$ de ses composantes (une partie à $p$ éléments : $N$ choix), puis l’ordre dans lequel on les énumère (une permutation de $A$ : $p!$ choix). Par le principe multiplicatif, le nombre de $p$-listes d’éléments distincts vaut $N\times p!$ ; or il vaut $\frac{n!}{(n-p)!}$, d’où $N=\frac{n!}{p!\,(n-p)!}$. Si $p>n$, aucune partie de $E$ n’a $p$ éléments et $\binom{n}{p}=0$.

Propriété — interprétations combinatoires. Soient $n\in\N^{*}$ et $p\in\Z$.

6Les modèles de tirage

On tire $p$ objets dans une urne contenant $n$ boules numérotées (donc discernables). Le tableau suivant donne le nombre de résultats possibles selon le protocole ; identifier le bon modèle est le premier réflexe de tout exercice.

Méthode — compter par le complémentaire. pour dénombrer les objets vérifiant « au moins un … », il est presque toujours plus court de compter tous les objets, puis de retirer ceux qui vérifient « aucun … » : $\Card A=\Card E-\Card\left(E\setminus A\right)$.

Méthode — compter par partition. pour dénombrer un ensemble $E$ difficile à décrire, trouver un paramètre (le cardinal, le plus petit élément, la valeur en un point fixé…), partitionner $E$ selon ce paramètre, compter chaque classe, puis sommer.

Méthode — double comptage. pour établir une identité, dénombrer un même ensemble de deux façons différentes ; les deux résultats sont alors égaux. C’est exactement ce que l’on a fait pour $\binom{n}{p}$, et ce que l’on fait pour Pascal et pour le binôme.