Ensembles, dénombrement et analyse combinatoire

Ensembles et relations fondamentales

L’appartenance d’un élément $x$ à un ensemble $A$ se note $x \in A$. Sa non-appartenance se note $x \notin A$.

Deux ensembles sont égaux lorsqu’ils ont exactement les mêmes éléments. Ainsi,

$$A=B \quad \Longleftrightarrow \quad A\subseteq B \text{ et } B\subseteq A.$$

L’inclusion stricte $A\subsetneq B$ signifie que $A\subseteq B$ et $A\neq B$.

Si $A$ possède $n$ éléments, chacun peut être retenu ou non dans une partie. Les choix étant indépendants, $\mathcal P(A)$ possède donc $2^n$ éléments.

Opérations ensemblistes

On se place dans un ensemble de référence $E$, qui contient tous les éléments considérés.

Les opérations d’union et d’intersection sont commutatives et associatives. Elles sont aussi distributives l’une par rapport à l’autre :

$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C),$$ $$A\cup(B\cap C)=(A\cup B)\cap(A\cup C).$$

Les lois de De Morgan décrivent le complémentaire d’une union ou d’une intersection :

$$(A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c.$$

L’ordre compte dans un couple : les rôles des deux coordonnées sont distincts.

Cardinal et partition d’un ensemble fini

Le cardinal de l’ensemble vide vaut $0$. Si $A\subseteq B$, alors $\lvert A\rvert\leq\lvert B\rvert$. Pour deux ensembles finis, le produit cartésien vérifie :

$$\lvert A\times B\rvert=\lvert A\rvert\,\lvert B\rvert.$$

Lorsque deux ensembles sont disjoints, le cardinal de leur union est la somme de leurs cardinaux. Dans le cas général, les éléments de l’intersection seraient comptés deux fois par cette somme : il faut donc les retrancher une fois.

Chaque élément de $E$ appartient alors à une et une seule partie de la partition. Si les parties sont $A_1,\ldots,A_k$, alors :

$$\lvert E\rvert=\sum_{i=1}^{k}\lvert A_i\rvert,$$

où $k$ est le nombre de parties et $i$ leur indice.

Principes fondamentaux du dénombrement

Le principe additif s’applique lorsqu’une situation se décompose en cas incompatibles : le nombre total est la somme des nombres associés à chaque cas.

Le principe multiplicatif s’applique à une succession de choix : si chaque choix d’une étape peut être associé à tous les choix de l’étape suivante, le nombre total est le produit des nombres de possibilités à chaque étape.

La convention $0!=1$ correspond au produit vide : il existe une seule manière de n’effectuer aucun choix et une seule manière d’ordonner un ensemble vide.