Sois le bienvenu ! On se retrouve aujourd'hui pour compter le nombre de parties d'un ensemble fini. Plus précisément, la propriété qu'on va démontrer, c'est que si on choisit n un antinaturel non nul, le nombre de parties d'un ensemble à n éléments, ça vaut 2 puissance n, qu'on peut aussi écrire comme la somme de p est égale à 0 à n des p parmi n. Donc avant de passer directement à la démonstration, on va se faire une petite idée des ingrédients qui vont être mis en jeu sur un exemple.
On va considérer pour ça un ensemble qui est constitué de trois éléments, une boule rouge, une boule bleue et une boule jaune. Et on va se demander ici, combien y a-t-il de parties de cet ensemble-là ? Alors, on peut les compter et on peut les ranger par nombre d'éléments. Dans un premier temps, il y a l'ensemble vide, donc il n'y a qu'une partie qui ne possède aucun élément.
Ensuite, pour les parties à un élément, j'ai la boule rouge toute seule, la boule bleue toute seule et la boule jaune toute seule. ce qui me donne donc trois nouvelles parties de cet ensemble là. Ensuite pour les ensembles à deux éléments, eh bien il y a celui où je n'ai pas choisi la boule jaune, celui où je n'ai pas choisi la boule bleue, celui où je n'ai pas choisi la boule rouge, ce qui donne trois nouvelles parties de cet ensemble là.
Et enfin la seule partie à trois éléments de mon ensemble, eh bien c'est lui-même, c'est la partie où il y a les trois boules. Et donc je retrouve ici finalement 1 plus 3 plus 3 plus 1, ça fait 8 parties de cet ensemble-là. Alors j'ai mis le plus ici dans le sens où c'est une disjonction de cas, soit j'ai zéro élément, soit j'en ai un, soit j'en ai deux, soit j'en ai trois.
Alors à l'issue de ce petit raisonnement-là, on peut se lancer dans la démonstration bien entendu, mais on peut aussi se demander finalement, c'est vrai que 8, c'est 2 puissance 3. Mais est-ce que c'est un miracle qu'on soit tombé sur 2 puissance 3, ou est-ce qu'on peut vraiment l'expliquer en faisant à nouveau quelque chose qui ressemble à du dénombrement ? Naturellement, on va l'expliquer. On va dire que pour construire une partie de cet ensemble-là, avec les trois boules, on pourrait raisonner comme suit.
Dans un premier temps, soit je choisis la boule rouge, soit je ne la choisis pas. Et ensuite, je passe à la boule bleue, et je me dis que soit je la choisis, soit je ne la choisis pas, que j'ai choisi la boule rouge ou non. Et ensuite, quels que soient les choix que j'ai réalisés sur la boule rouge et sur la boule bleue, soit je choisis la boule jaune, soit je ne la choisis pas.
Et donc tu vois que sur cet arbre binaire ici, à la sortie de chaque branche correspond une partie de mon ensemble. Par exemple sur cette branche là, j'ai choisi la boule rouge, pas la boule bleue et la boule jaune. Et donc ça correspond à cette partie là, où il y a la boule rouge et la boule jaune. Donc finalement, combien y a-t-il de parties de l'ensemble si je compte comme ça ?
Eh bien j'ai deux choix pour la boule rouge, soit je la choisis, soit je ne la choisis pas, et aussi il me faut choisir la boule bleue, donc ça me donne deux nouveaux choix, et enfin la boule jaune, donc deux nouveaux choix, et donc ça me donne bien 2 puissance 3 qui vaut 8. Alors ici on illustre des principes très intéressants du dénombrement, qui est par exemple que lorsqu'on utilise la conjonction et il va s'agir d'un principe multiplicatif, et de l'autre côté, sur l'exemple du dessus, comme il s'agissait de contenir zéro élément ou un élément. ou deux ou trois, il s'agit ici d'une disjonction de cas et c'est pour cette raison qu'on retrouve un principe additif. Donc on a ces deux façons de compter en comptant par nombre d'éléments et en comptant le nombre de chemins sur un arbre binaire et on a maintenant tous les éléments qu'il nous faut pour nous lancer sereinement dans la démonstration.
Donc on va choisir E, un ensemble à n éléments et tâchons de compter son nombre de parties. La première méthode, c'est celle qu'on a fait dans l'exemple, c'est de classer ces parties par nombre d'éléments. On va dire pour cela que pour tout entier naturel P, compris entre 0 et n, il y a exactement P parmi n parties à P éléments dans cet ensemble. Et c'est d'ailleurs comme ça qu'on peut définir raisonnablement les coefficients binomiaux.
Alors dans l'exemple, c'est exactement ce qu'on retrouve, puisque 1, 3, 3 et 1 correspondent respectivement à 0 parmi 3, 1 parmi 3, 2 parmi 3 et 3 parmi 3. Et donc au total, il va y avoir 0 parmi n, plus 1 parmi n, plus etc. jusqu'à n parmi n. n, ce que j'écris comme ceci, somme de p est égal à 0 à n des p parmi n, partie dans l'ensemble e. Donc pour cette méthode là c'est très simple et c'est allé très vite, comme tu peux le voir. Pour la deuxième méthode, je te propose quelque chose d'assez rigoureux que j'appellerai codage binaire. Pour ça on va numéroter les éléments de e et on va les appeler x1, x2 jusqu'à xn.
Et on va reprendre sur l'exemple cette affaire d'arbres. Je vais me dire que choisir la boule et la boule bleue et la boule jaune, je vais coder ça par le triplet. De la même manière, si je choisis la boule rouge et la bleue mais pas la jaune, je vais coder par.
Et donc le dernier, si je ne choisis ni la rouge, ni la bleue, ni la jaune, je vais coder 0 0 0. Si tu as de la suite dans les idées, tu auras compris que 1 désigne ainsi la présence d'une boule, et que 0 désigne l'absence d'une boule donnée. Et donc on va écrire ça proprement dans la démonstration. On va dire qu'à chaque partie A de l'ensemble E, on peut associer un unique NUPLAY dont les coordonnées sont des éléments de 0, 1, de la manière suivante. Si XK appartient à A, alors la quaième coordonnée du NUPLAY vaut 1. Si XK n'appartient pas à A, cette coordonnée vaut 0. Donc c'est exactement ce qu'on a fait sur l'exemple si contre. Mais ça marche aussi dans l'autre sens. C'est-à-dire que si tu me dis 1, 0, 1 dans l'exemple précédent, je comprendrais qu'il faut que je choisisse la boule rouge, pas la bleue, et que je choisisse la jaune, et ça va donc correspondre à cette partie-là de mon ensemble constitué de trois boules.
Et c'est exactement ce qu'on va dire ici. On va dire que réciproquement, à chaque NUPLAY dont les coordonnées sont soit 0 soit 1, on peut associer une unique partie A de l'ensemble E qui correspond selon le protocole précédent à ce NUPLAY, puisqu'en fait à chaque fois, la présence ou l'absence de chaque XK dans l'ensemble A est donnée par la valeur de la quête. quatrième coordonnée de ce anuplet, sachant que si elle vaut 1, ça désigne la présence, et si elle vaut 0, ça désigne l'absence. Et donc ça permet de conclure, puisque finalement, à chaque partie de E, on a associé un élément de l'ensemble 0, 1 puissance n, et réciproquement, ça marche dans les deux sens. Donc on va dire qu'il y a autant de parties dans E que d'éléments dans cet ensemble-là, 0, 1 puissance n. et cet ensemble, on connaît très bien son nombre d'éléments, ça vaut 2 puissance n.
C'est le produit cartésien de n ensembles à deux éléments, donc ça compte 2 x 2 x 2, etc. 2 puissance n éléments. Et donc ça me permet de conclure à l'égalité de la propriété, puisque finalement j'ai compté deux fois la même chose de deux manières différentes, donc les deux quantités qui sont encadrées en rouge sont égales. Alors pour terminer, je mentionne ici le fait que tu peux retrouver cette formule-là, cette égalité, grâce à la formule du binôme de Newton, que je démontre dans une autre émission de cette série, démonstration de terminale numéro 3. J'espère que cette émission t'a plu, je te souhaite une excellente journée, et je te dis à la prochaine.
Sous-titres par Jérémy Diaz