02 · Ensembles¶
Intuition
Un ensemble est une collection d'objets, sans ordre et sans répétition. C'est volontairement le concept le plus pauvre possible — et c'est précisément ce qui le rend universel : les nombres, les fonctions, les événements probabilistes, les états d'un programme, tout se décrit avec des ensembles.
Ce chapitre est court en contenu et long en conséquences. Il fournit le vocabulaire des probabilités du même semestre, où « événement » signifiera exactement « partie de l'univers », et où « \(A\) ou \(B\) » sera littéralement \(A \cup B\).
1. Définitions de base¶
1.1 Ensemble, élément, appartenance¶
Un ensemble est une collection d'objets appelés ses éléments. On écrit \(x \in E\) pour « \(x\) est un élément de \(E\) », et \(x \notin E\) sinon.
Deux façons de décrire un ensemble :
Ni ordre, ni multiplicité
\(\{1,2,3\}\), \(\{3,1,2\}\) et \(\{1,1,2,3,3\}\) désignent le même ensemble. Un ensemble ne retient que « qui est dedans », pas « combien de fois » ni « dans quel ordre ».
C'est une différence essentielle avec les listes et les tableaux en informatique — et avec les arrangements du chapitre 04, où l'ordre compte au contraire.
1.2 L'ensemble vide¶
L'ensemble sans aucun élément. Il est unique, et il est inclus dans tout ensemble.
Ne pas confondre trois objets
- \(\varnothing\) : l'ensemble vide, qui a 0 élément ;
- \(\{\varnothing\}\) : un ensemble contenant l'ensemble vide, donc 1 élément ;
- \(\{0\}\) : un ensemble contenant le nombre zéro, donc 1 élément, mais pas le même.
Cette distinction paraît byzantine. Elle est pourtant exactement celle entre « aucun résultat », « un résultat qui est la liste vide », et « un résultat qui vaut zéro » — trois situations que confond régulièrement du code mal écrit.
1.3 Cardinal¶
Le cardinal de \(E\), noté \(\operatorname{Card}(E)\) ou \(|E|\), est son nombre d'éléments quand \(E\) est fini.
2. Inclusion¶
« \(A\) est inclus dans \(B\) », ou « \(A\) est une partie de \(B\) ».
Comment démontrer une inclusion
Toujours de la même façon : « Soit \(x \in A\). Montrons que \(x \in B\). » Puis on raisonne sur \(x\).
C'est le squelette obligé, et il ne varie jamais.
Propriétés :
- \(\varnothing \subset A\) pour tout \(A\) ;
- \(A \subset A\) ;
- si \(A\subset B\) et \(B \subset C\) alors \(A \subset C\) (transitivité).
2.1 Égalité par double inclusion¶
La méthode de référence
Pour démontrer que deux ensembles sont égaux, on montre les deux inclusions. C'est la technique standard de tout le chapitre, et elle resservira en probabilités, en logique et en théorie des langages.
2.2 Ensemble des parties¶
L'ensemble de toutes les parties de \(E\) se note \(\mathcal{P}(E)\).
Théorème du cardinal
Si \(\operatorname{Card}(E) = n\), alors
Démonstration
Construire une partie de \(E\), c'est décider pour chaque élément s'il y est ou non : deux choix indépendants par élément, donc \(2 \times 2 \times \dots \times 2 = 2^n\) parties.
Formellement, l'application qui à une partie \(A\) associe le mot binaire \((b_1,\dots,b_n)\) avec \(b_i = 1\) si le \(i\)-ème élément est dans \(A\), est une bijection de \(\mathcal{P}(E)\) vers \(\{0,1\}^n\). On établira ce type d'argument au chapitre 03. \(\blacksquare\)
Lecture informatique
Cette bijection est exactement la représentation d'un ensemble par un
masque de bits. Un int 64 bits code toutes les parties d'un ensemble
de 64 éléments, l'union devient un OR binaire, l'intersection un AND, le
complémentaire un NOT. C'est la structure de données utilisée dans les
solveurs SAT et les moteurs d'échecs (bitboards).
3. Opérations¶
Soient \(A\) et \(B\) des parties d'un ensemble de référence \(E\).
| Opération | Notation | Définition | Lecture logique |
|---|---|---|---|
| Réunion | \(A \cup B\) | \(\{x \mid x\in A \text{ ou } x \in B\}\) | ou (inclusif) |
| Intersection | \(A \cap B\) | \(\{x \mid x\in A \text{ et } x \in B\}\) | et |
| Différence | \(A \setminus B\) | \(\{x \mid x\in A \text{ et } x \notin B\}\) | et non |
| Complémentaire | \(\overline{A}\) ou \(A^c\) | \(E \setminus A\) | non |
| Diff. symétrique | \(A \Delta B\) | \((A\setminus B)\cup(B\setminus A)\) | ou exclusif |
Le « ou » mathématique est inclusif
\(x \in A\cup B\) est vrai aussi quand \(x\) est dans les deux. Le « ou » exclusif du langage courant (« fromage ou dessert ») correspond à la différence symétrique \(A \Delta B\), pas à la réunion.
3.1 Propriétés algébriques¶
Commutativité et associativité : \(\cup\) et \(\cap\) se comportent comme l'addition et la multiplication.
Distributivité — dans les deux sens, contrairement à \(+\) et \(\times\) :
Une dissymétrie qui disparaît
En arithmétique, \(\times\) se distribue sur \(+\) mais pas l'inverse : \(a+(b\times c) \neq (a+b)(a+c)\). Pour les ensembles, la distributivité est symétrique. C'est une des raisons pour lesquelles \((\mathcal{P}(E), \cup, \cap)\) n'est pas un anneau ordinaire mais une algèbre de Boole.
3.2 Lois de De Morgan¶
En français : la négation d'un « ou » est un « et » de négations, et réciproquement.
« Il n'est ni grand ni riche » = « il n'est pas (grand ou riche) » = « il n'est pas grand et il n'est pas riche ».
Démonstration de la première loi, par double inclusion
Sens \(\subset\). Soit \(x \in \overline{A\cup B}\). Alors \(x \notin A\cup B\), c'est-à-dire qu'il est faux que (\(x\in A\) ou \(x \in B\)). Par négation d'un « ou », \(x\notin A\) et \(x\notin B\). Donc \(x \in \overline A\) et \(x \in \overline B\), soit \(x \in \overline A \cap \overline B\).
Sens \(\supset\). Soit \(x \in \overline A\cap\overline B\). Alors \(x\notin A\) et \(x\notin B\), donc \(x\) n'est ni dans l'un ni dans l'autre, donc \(x \notin A\cup B\), soit \(x\in\overline{A\cup B}\).
\(\blacksquare\)
Où De Morgan resservira
- En probabilités : calculer \(P(\text{au moins un})\) via \(1 - P(\text{aucun})\) est une application directe.
- En logique propositionnelle (module LOMA12, S2) : les mêmes lois s'écrivent \(\lnot(p\lor q) \equiv \lnot p \land \lnot q\).
- En programmation :
!(a || b)équivaut à!a && !b. La simplification de conditions booléennes est littéralement du De Morgan.
3.3 Formule du crible (deux ensembles)¶
Pourquoi le terme correctif : en additionnant les cardinaux, on compte deux fois les éléments de l'intersection. On les retranche une fois.
Pour trois ensembles :
Les signes alternent. C'est le principe d'inclusion-exclusion, qu'on retrouvera en combinatoire.
4. Produit cartésien¶
L'ensemble des couples dont la première coordonnée est dans \(A\) et la seconde dans \(B\).
Un couple n'est pas une paire
\((a,b)\) est un couple : il est ordonné, et \((a,b) \neq (b,a)\) dès que \(a \neq b\).
\(\{a,b\}\) est une paire : c'est un ensemble, donc \(\{a,b\} = \{b,a\}\).
Notation : parenthèses pour l'ordonné, accolades pour le non ordonné.
Cardinal :
C'est le principe multiplicatif, base de toute la combinatoire.
Notation puissance : \(A^n = A\times A\times\dots\times A\) (\(n\) facteurs), l'ensemble des \(n\)-uplets. Par exemple \(\mathbb{R}^3\) est l'ensemble des triplets de réels, et \(\{0,1\}^8\) celui des octets — de cardinal \(2^8 = 256\).
5. Partitions¶
Une partition de \(E\) est une famille de parties \(A_1, \dots, A_n\) telles que :
- aucune n'est vide : \(A_i \neq \varnothing\) ;
- elles sont deux à deux disjointes : \(A_i \cap A_j = \varnothing\) pour \(i\neq j\) ;
- elles recouvrent \(E\) : \(A_1\cup\dots\cup A_n = E\).
Conséquence sur les cardinaux :
(Pas de terme correctif : les intersections sont vides.)
Où cela mène directement
En probabilités, une partition de l'univers s'appelle un système complet d'événements, et c'est l'hypothèse exacte de la formule des probabilités totales :
Voir Probabilités 04.
Exemples traités¶
Exemple 1 — Calcul d'opérations
Soit \(E = \{1,2,\dots,10\}\), \(A = \{2,4,6,8,10\}\) (pairs), \(B = \{1,2,3,4,5\}\).
- \(A\cap B = \{2,4\}\)
- \(A\cup B = \{1,2,3,4,5,6,8,10\}\)
- \(A\setminus B = \{6,8,10\}\)
- \(B\setminus A = \{1,3,5\}\)
- \(\overline A = \{1,3,5,7,9\}\)
- \(A\Delta B = \{1,3,5,6,8,10\}\)
Vérification par le crible : \(\operatorname{Card}(A\cup B) = 5+5-2 = 8\), et on compte bien 8 éléments ✓
Exemple 2 — Démonstration par double inclusion
Montrer que \(A\setminus(B\cap C) = (A\setminus B)\cup(A\setminus C)\).
Sens \(\subset\). Soit \(x \in A\setminus(B\cap C)\). Alors \(x\in A\) et \(x\notin B\cap C\). Cette seconde condition signifie qu'il est faux que (\(x\in B\) et \(x\in C\)), donc \(x\notin B\) ou \(x\notin C\).
- Si \(x\notin B\) : alors \(x\in A\setminus B\).
- Si \(x\notin C\) : alors \(x\in A\setminus C\).
Dans les deux cas \(x\in(A\setminus B)\cup(A\setminus C)\).
Sens \(\supset\). Soit \(x\in(A\setminus B)\cup(A\setminus C)\).
- Si \(x\in A\setminus B\) : \(x\in A\) et \(x\notin B\), donc a fortiori \(x\notin B\cap C\).
- Si \(x\in A\setminus C\) : \(x\in A\) et \(x\notin C\), donc \(x\notin B\cap C\).
Dans les deux cas \(x\in A\) et \(x\notin B\cap C\). \(\blacksquare\)
Lecture De Morgan
En posant \(A\setminus X = A\cap\overline X\), l'identité devient \(A\cap\overline{B\cap C} = (A\cap\overline B)\cup(A\cap\overline C)\), qui est De Morgan suivi de la distributivité. Reconnaître cette structure évite la double inclusion.
Exemple 3 — Ensemble des parties
Lister \(\mathcal{P}(\{a,b,c\})\).
Huit parties, soit \(2^3\) ✓. Organisées par cardinal : 1 partie de cardinal 0, 3 de cardinal 1, 3 de cardinal 2, 1 de cardinal 3 — soit \(1, 3, 3, 1\), la quatrième ligne du triangle de Pascal. Ce n'est pas un hasard, on le verra au chapitre 04.
Exemple 4 — Crible sur un cas concret
Sur 100 étudiants : 60 font de l'anglais, 45 de l'espagnol, 20 font les deux. Combien n'en font aucune ?
Donc \(100 - 85 = 15\) étudiants ne suivent aucune des deux langues.
Vérification par partition : anglais seul \(= 40\), espagnol seul \(= 25\), les deux \(= 20\), aucune \(= 15\). Total \(= 100\) ✓
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| \(\{3\} \in \mathbb{N}\) | \(3 \in \mathbb{N}\), \(\{3\}\subset\mathbb{N}\) |
| \(\varnothing = \{\varnothing\}\) | Cardinaux 0 et 1 |
| \((a,b) = \{a,b\}\) | Couple ordonné ≠ paire |
| \(\operatorname{Card}(A\cup B) = \operatorname{Card}A + \operatorname{Card}B\) | Faux si \(A\cap B \neq\varnothing\) |
| \(\overline{A\cup B} = \overline A\cup\overline B\) | De Morgan échange \(\cup\) et \(\cap\) |
| Démontrer \(A=B\) par une seule inclusion | Il en faut deux |
Exercices¶
★ Exercice 1. Soit \(E = \{1,\dots,12\}\), \(A\) l'ensemble des multiples de 2, \(B\) celui des multiples de 3.
Déterminer \(A\), \(B\), \(A\cap B\), \(A\cup B\), \(A\setminus B\), \(\overline{A\cup B}\), et vérifier la formule du crible.
★ Exercice 2. Donner \(\mathcal{P}(E)\) pour \(E = \{1,2\}\), puis pour \(E = \varnothing\). Vérifier le cardinal dans les deux cas.
★★ Exercice 3. Soit \(E\) un ensemble et \(A, B \subset E\). Démontrer par double inclusion :
a) \(\overline{A\cap B} = \overline A\cup\overline B\) b) \(A\setminus B = A\cap\overline B\) c) \(A\subset B \iff A\cap B = A\)
★★ Exercice 4. Dans une promotion de 80 apprentis, 50 savent programmer en Python, 35 en Java, et 12 ne savent ni l'un ni l'autre.
a) Combien savent les deux ? b) Combien savent exactement un des deux langages ?
★★ Exercice 5. Déterminer si les affirmations suivantes sont vraies. Si elles sont fausses, donner un contre-exemple.
a) \(A\cup B = A\cup C \implies B = C\) b) \(A\cap B = A\cap C \implies B = C\) c) \(\big(A\cup B = A\cup C \text{ et } A\cap B = A\cap C\big) \implies B=C\)
★★★ Exercice 6. Soient \(A\), \(B\) deux parties de \(E\). Démontrer que
Puis montrer que \(\Delta\) est associative : \((A\Delta B)\Delta C = A\Delta(B\Delta C)\).
Indication : caractérisez l'appartenance à \(A\Delta B\Delta C\) par la parité du nombre d'ensembles contenant \(x\).
★★★ Exercice 7. Soit \(E\) un ensemble fini de cardinal \(n\).
a) Combien y a-t-il de couples \((A,B)\) de parties de \(E\) telles que \(A\subset B\) ? Indication : raisonnez élément par élément — chaque élément a trois statuts possibles. b) Combien y a-t-il de couples \((A,B)\) tels que \(A\cap B = \varnothing\) ?
★★★ Exercice 8. Démontrer la formule du crible pour trois ensembles :
Indication : appliquez deux fois la formule à deux ensembles, en posant \(D = B\cup C\).
★★★★ Exercice 9. Combien y a-t-il de partitions de \(\{1,2,3\}\) ? de \(\{1,2,3,4\}\) ?
Ces nombres s'appellent les nombres de Bell. Cherchez-les à la main, puis proposez une relation de récurrence en raisonnant sur le bloc contenant l'élément 1.
★★★★ Exercice 10 — lien informatique. On représente une partie de \(E = \{0,1,\dots,63\}\) par un entier non signé 64 bits : le bit \(i\) vaut 1 si et seulement si \(i\) appartient à la partie.
a) À quelles opérations sur les entiers correspondent \(\cup\), \(\cap\), \(\overline{\ \cdot\ }\) et \(\Delta\) ? b) Traduire les lois de De Morgan en identités sur les opérateurs binaires. c) Comment tester \(A\subset B\) en une seule opération ? d) Justifier que cette représentation est exacte — c'est-à-dire que l'application « partie \(\mapsto\) entier » est bijective — et relier ce fait au théorème \(\operatorname{Card}(\mathcal{P}(E)) = 2^n\).
Corrigés¶
Corrigé — Exercice 1
\(A = \{2,4,6,8,10,12\}\), \(\operatorname{Card}A = 6\). \(B = \{3,6,9,12\}\), \(\operatorname{Card}B = 4\).
- \(A\cap B = \{6,12\}\) (multiples de 6), cardinal 2.
- \(A\cup B = \{2,3,4,6,8,9,10,12\}\), cardinal 8.
- \(A\setminus B = \{2,4,8,10\}\), cardinal 4.
- \(\overline{A\cup B} = \{1,5,7,11\}\), cardinal 4.
Crible : \(6+4-2 = 8\) ✓ et \(12 - 8 = 4\) ✓
Corrigé — Exercice 2
\(\mathcal{P}(\{1,2\}) = \big\{\varnothing,\{1\},\{2\},\{1,2\}\big\}\) — 4 éléments, soit \(2^2\) ✓
\(\mathcal{P}(\varnothing) = \{\varnothing\}\) — 1 élément, soit \(2^0 = 1\) ✓
Warning
\(\mathcal{P}(\varnothing)\) n'est pas vide : il contient exactement une partie, l'ensemble vide lui-même.
Corrigé — Exercice 3
a) Sens \(\subset\). Soit \(x\in\overline{A\cap B}\). Alors \(x\notin A\cap B\), donc il est faux que (\(x\in A\) et \(x\in B\)), donc \(x\notin A\) ou \(x\notin B\), donc \(x\in\overline A\cup\overline B\).
Sens \(\supset\). Soit \(x\in\overline A\cup\overline B\). Alors \(x\notin A\) ou \(x\notin B\). Dans les deux cas, \(x\) ne peut pas être dans les deux à la fois, donc \(x\notin A\cap B\), donc \(x\in\overline{A\cap B}\). \(\blacksquare\)
b) \(x\in A\setminus B \iff (x\in A\) et \(x\notin B) \iff (x\in A\) et \(x\in\overline B) \iff x\in A\cap\overline B\).
L'équivalence étant directe à chaque étape, les deux inclusions sont simultanées. \(\blacksquare\)
c) Sens \(\implies\). Supposons \(A\subset B\). \(A\cap B\subset A\) est toujours vrai. Réciproquement, soit \(x\in A\) ; comme \(A\subset B\), \(x\in B\), donc \(x\in A\cap B\). D'où \(A\subset A\cap B\), et l'égalité.
Sens \(\impliedby\). Supposons \(A\cap B = A\). Soit \(x\in A\). Alors \(x\in A\cap B\), donc \(x\in B\). D'où \(A\subset B\). \(\blacksquare\)
Corrigé — Exercice 4
a) \(\operatorname{Card}(P\cup J) = 80-12 = 68\). Par le crible : \(68 = 50+35 - \operatorname{Card}(P\cap J)\), donc
17 apprentis connaissent les deux.
b) Exactement un : \(\operatorname{Card}(P\Delta J) = 68 - 17 = 51\).
Détail : Python seul \(= 50-17 = 33\), Java seul \(= 35-17 = 18\), total \(51\) ✓
Corrigé — Exercice 5
a) Faux. \(A = \{1\}\), \(B = \varnothing\), \(C = \{1\}\). \(A\cup B = A\cup C = \{1\}\), mais \(B\neq C\).
b) Faux. \(A = \varnothing\), \(B = \{1\}\), \(C = \{2\}\). \(A\cap B = A\cap C = \varnothing\), mais \(B\neq C\).
c) Vrai. Démontrons-le. Soit \(x\in B\).
Alors \(x\in A\cup B = A\cup C\), donc \(x\in A\) ou \(x\in C\).
- Si \(x\in C\), c'est fini.
- Si \(x\in A\) : alors \(x\in A\cap B = A\cap C\), donc \(x\in C\).
Dans les deux cas \(x\in C\), donc \(B\subset C\). Par symétrie des hypothèses en \(B\) et \(C\), on a aussi \(C\subset B\). D'où \(B = C\). \(\blacksquare\)
La leçon
Connaître la réunion ou l'intersection avec \(A\) ne suffit pas ; les deux ensemble déterminent \(B\). C'est l'analogue ensembliste du fait que connaître \(a+b\) et \(a \cdot b\) détermine \(\{a,b\}\).
Corrigé — Exercice 6
Première identité.
\(\subset\). Soit \(x\in A\Delta B\), donc \(x\in A\setminus B\) ou \(x\in B\setminus A\). Dans les deux cas \(x\) appartient à exactement un des deux ensembles : donc \(x\in A\cup B\) et \(x\notin A\cap B\).
\(\supset\). Soit \(x\in(A\cup B)\setminus(A\cap B)\). Alors \(x\) est dans au moins un des deux et pas dans les deux : il est donc dans exactement un, c'est-à-dire dans \(A\setminus B\) ou dans \(B\setminus A\). \(\blacksquare\)
Associativité. Caractérisons l'appartenance. Pour \(x\) donné, notons \(n(x)\) le nombre d'ensembles parmi \(A\), \(B\), \(C\) qui contiennent \(x\) (donc \(n(x)\in\{0,1,2,3\}\)).
On vérifie d'abord que \(x\in A\Delta B\) si et seulement si \(x\) appartient à un nombre impair parmi \(\{A,B\}\).
Calculons \((A\Delta B)\Delta C\). On a \(x\in(A\Delta B)\Delta C\) ssi \(x\) appartient à un nombre impair parmi \(\{A\Delta B, C\}\), c'est-à-dire :
- \(x\in A\Delta B\) et \(x\notin C\) : nombre impair parmi \(\{A,B\}\), plus 0 ;
- ou \(x\notin A\Delta B\) et \(x\in C\) : nombre pair parmi \(\{A,B\}\), plus 1.
Dans les deux cas, \(n(x)\) est impair.
Le même raisonnement sur \(A\Delta(B\Delta C)\) donne la même caractérisation : \(n(x)\) impair. Les deux ensembles ont donc les mêmes éléments. \(\blacksquare\)
Lecture algébrique
La différence symétrique est l'addition modulo 2 sur les vecteurs
d'appartenance. C'est exactement le XOR binaire — d'où l'associativité,
héritée de celle de l'addition dans \(\mathbb{Z}/2\mathbb{Z}\).
\((\mathcal{P}(E), \Delta, \cap)\) est d'ailleurs un anneau, d'élément
neutre \(\varnothing\) pour \(\Delta\), où chaque élément est son propre
opposé : \(A\Delta A = \varnothing\).
Corrigé — Exercice 7
a) Raisonnons élément par élément. Pour chaque \(x\in E\), la contrainte \(A\subset B\) laisse exactement trois possibilités :
| \(x \in A\) ? | \(x\in B\) ? | Autorisé ? |
|---|---|---|
| non | non | ✓ |
| non | oui | ✓ |
| oui | oui | ✓ |
| oui | non | ✗ (violerait \(A\subset B\)) |
Les \(n\) choix étant indépendants, il y a \(3^n\) couples.
Vérification \(n=1\), \(E=\{a\}\) : les couples sont \((\varnothing,\varnothing)\), \((\varnothing,\{a\})\), \((\{a\},\{a\})\) — trois ✓
b) Même méthode. Pour \(A\cap B=\varnothing\), chaque élément est soit dans \(A\) seul, soit dans \(B\) seul, soit dans aucun — jamais dans les deux. Trois possibilités par élément, donc \(3^n\) également.
Pourquoi le même résultat
Les deux comptages sont en bijection : \((A,B)\) avec \(A\subset B\) correspond à \((A, \overline B)\) avec intersection vide. La bijection explique la coïncidence, qui n'en est pas une.
Corrigé — Exercice 8
Posons \(D = B\cup C\) et appliquons le crible à deux ensembles :
Premier terme correctif : \(\operatorname{Card}D = \operatorname{Card}B + \operatorname{Card}C - \operatorname{Card}(B\cap C)\).
Second : par distributivité, \(A\cap D = A\cap(B\cup C) = (A\cap B)\cup(A\cap C)\), donc à nouveau par le crible :
Or \((A\cap B)\cap(A\cap C) = A\cap B\cap C\).
En rassemblant :
C'est la formule annoncée. \(\blacksquare\)
Vérification numérique. \(A=\{1,2,3\}\), \(B=\{2,3,4\}\), \(C=\{3,4,5\}\) :
Et \(A\cup B\cup C = \{1,2,3,4,5\}\), de cardinal 5 ✓
Corrigé — Exercice 9
Partitions de \(\{1,2,3\}\) :
- \(\{\{1\},\{2\},\{3\}\}\)
- \(\{\{1,2\},\{3\}\}\)
- \(\{\{1,3\},\{2\}\}\)
- \(\{\{2,3\},\{1\}\}\)
- \(\{\{1,2,3\}\}\)
\(B_3 = 5\).
Partitions de \(\{1,2,3,4\}\) : on en compte 15 (1 en un bloc, 7 en deux blocs, 6 en trois blocs, 1 en quatre blocs). \(B_4 = 15\).
Relation de récurrence. Raisonnons sur le bloc contenant l'élément 1. Si ce bloc contient \(k\) autres éléments, il y a \(\binom{n-1}{k}\) façons de les choisir parmi les \(n-1\) restants, et les \(n-1-k\) éléments non choisis forment une partition arbitraire, soit \(B_{n-1-k}\) possibilités.
(Le second membre s'obtient par le changement d'indice \(j = n-1-k\) et la symétrie \(\binom{n-1}{k} = \binom{n-1}{n-1-k}\), vue au chapitre 04.)
Vérification. \(B_0 = 1\), \(B_1 = 1\). \(B_2 = \binom10 B_0 + \binom11 B_1 = 1+1 = 2\) ✓ \(B_3 = \binom20 B_0+\binom21 B_1+\binom22 B_2 = 1+2+2 = 5\) ✓ \(B_4 = 1+3\times1+3\times2+1\times5 = 15\) ✓
Les nombres de Bell croissent très vite : \(B_5 = 52\), \(B_{10} = 115\,975\).
Corrigé — Exercice 10
a) Avec \(a\) et \(b\) les entiers codant \(A\) et \(B\) :
| Ensemble | Bits |
|---|---|
| \(A\cup B\) | a \| b (OR) |
| \(A\cap B\) | a & b (AND) |
| \(\overline A\) | ~a (NOT) |
| \(A\Delta B\) | a ^ b (XOR) |
| \(A\setminus B\) | a & ~b |
b) De Morgan devient
Ce sont des identités que tout compilateur applique lors de la simplification des expressions booléennes.
c) \(A\subset B\) équivaut à \(A\cap B = A\) (exercice 3c), soit
(a & b) == a. Autre écriture équivalente : (a & ~b) == 0, qui traduit
« \(A\setminus B\) est vide ».
d) L'application \(\varphi : \mathcal{P}(E) \to \{0,1\}^{64}\) qui à une partie associe son vecteur d'appartenance est bijective :
- injective — deux parties distinctes diffèrent par au moins un élément, donc par au moins un bit ;
- surjective — tout mot binaire décrit une partie, celle des indices dont le bit vaut 1.
Un mot de 64 bits est un entier de \([\![0; 2^{64}-1]\!]\), il y en a donc exactement \(2^{64}\). Par la bijection, \(\operatorname{Card}(\mathcal{P}(E)) = 2^{64}\), ce qui est le théorème du cardinal avec \(n = 64\).
Chapitre suivant : Applications : injection, surjection, bijection.