[SON] [AUDIO_VIDE] Nous allons passer à la séance d'exercice 3 du cours 1, et comme je l'avais annoncé précédemment, nous allons voir une application de la formule du crible ou de la formule dite d'inclusion-exclusion. Et nous allons voir ce que j'appelle la distribution aléatoire du courrier : on imagine un facteur qui doit distribuer n lettres, adressées à n destinataires qui sont distincts, et en fait, ce facteur est complètement ivre, et il dépose une lettre au hasard, dans chaque boîte. Il ne se préoccupe pas du destinataire. La question qu'on se pose, c'est : quelle est la probabilité d'obtenir une distribution correcte du courrier? Autrement dit, quelle est la probabilité que chaque lettre arrive à un bon destinataire? Deuxième question qu'on se pose, c'est : quelle est la probabilité qu'au moins une lettre parvienne au bon destinataire? Une troisième question, qui est bien sûr reliée à la précédente, c'est : quelle est la probabilité qu'aucune lettre n'arrive au bon destinataire? Et enfin, on se demandera quel est le nombre, qu'on va appeler dn, de manières différentes de poster les lettres, de telle sorte qu'aucune n'arrive à destination? Et nous allons voir que, si on sait utiliser la formule d'inclusion-exclusion, on arrive facilement à résoudre ce problème ; sans cette formule, ce serait plus compliqué. Donc, en ce qui concerne la première question, comme le facteur distribue de façon équiprobable les lettres, il y a tout simplement factorielle n façons de poster les n lettres, et bien sûr, comme chaque lettre a un destinataire, et un seul qui est correct, il y a une seule façon de poster les lettres correctement. Autrement dit, la probabilité que l'on recherche, c'est tout simplement 1 / n!. Donc ça c'est très simple. Pour répondre à la deuxième question, qui est de savoir quelle est la probabilité qu'au moins une lettre parvienne au bon destinataire, on va numéroter de 1 à n les lettres, dans un ordre quelconque, on choisit un ordre, et on numérote avec les mêmes numéros les boîtes des bons destinataires. Et donc, on va introduire un événement Ai, qui va être : la lettre numéro i arrive dans la boîte numéro i, autrement dit, la lettre en question arrive dans la bonne boîte, arrive au bon destinataire. Donc, maintenant, l'événement qui nous intéresse, c'est : au moins une lettre arrive au bon destinataire. Et donc, en vertu des propriétés ensemblistes que nous avons étudiées, l'événement en question, que je note E, c'est tout simplement l'union de A1, A2,... An. Qui est bien, donc : il y a au moins une lettre qui arrive au bon destinataire. Et donc, on se retrouve à vouloir calculer la possibilité d'une union finie d'événements, et puisque nous avons vu dans la séance 2 la formule d'inclusion-exclusion, nous allons nous empresser de l'appliquer. Et si j'écris la formule générale à nouveau, nous avons que la probabilité de E, c'est donc la somme de 1 jusqu'à n (-1 puissance (k+1) ), donc on somme ces signes alternés, et pour chaque k, on a ces k-uplets d'événements, dont on regarde les intersections. Et cette formule nous donne, normalement, la probabilité de E. Maintenant, on va essayer de calculer la probabilité de ces intersections. Donc, on se demande : que vaut P(Ai1, inter Ai2,... Aik), pour un k quelconque? Donc, si on prend le cas où k = 1 donc, il n'y a que un seul événement à chaque fois, c'est facile de voir que P(Ai) = (n- 1 factorielle) / n factorielle tout simplement parce que si l'on suppose qu'il y a une lettre qui est arrivée au bon destinataire, et indépendamment de toutes les autres, qui elles, ont été distribuées complètement au hasard, les n-1 qui restent, pour les distribuer au hasard, il y a ( n- 1 )! possibilités. Donc, la probabilité qu'on ait mis une lettre dans la bonne boîte aux lettres, c'est ( n- 1 )! / n!. Et vous voyez, assez immédiatement, la généralisation : on pourrait prendre 2 lettres, en supposant qu'on en ait deux, quelconques, qui sont dans leurs boîtes respectives, et on peut deviner facilement, que la probabilité qu'on ait k lettres qui ont été correctement mises dans leurs boîtes aux lettres associées, c'est tout simplement ( n- k )! / n!, pour le même raisonnement que j'ai tenu tout à l'heure. Vous constatez en particulier, que cette probabilité ne dépend absolument pas des événements eux-mêmes, elle ne dépend que du nombre d'événements qui sont mis en jeu, donc il y en a k. Donc cette probabilité dépend de n et de k seulement, et quand on injecte ça dans la formule de l'inclusion-exclusion, voilà ce que l'on obtient : Donc, j'ai réécrit la première ligne de la formule, telle quelle, et sur la deuxième ligne, vous voyez, puisque chacune de ces intersections a une probabilité qui ne dépend que de la cardinalité, ça nous donne ce (n- k )! / n!, et tout simplement, il faut compter combien on a de k-uplets, quand on a ordonné comme ça. Et donc, c'est tout simplement k parmi n possibilités On se retrouve donc avec cette somme, qui est : -1 puissance ( k + 1 ), k parmi n, et ensuite, fois ( n- k )! / n!, et en utilisant la définition du coefficient binomial, il y a une simplification qui se fait, et il ne reste plus que le k!, qui vient du coefficient binomial. Donc, on obtient que la probabilité de E, c'est cette somme qui est en bas à droite, et c'est une somme qui fait penser tout-de-suite à une exponentielle, donc en fait un petit calcul montre que, déjà quand n tend vers l'infini, P(E) tend tout simplement vers 1- exponentielle de -1, et si vous prenez une calculette, vous verrez que c'est approximativement, 0.632. Ce qui est remarquable, c'est que, en fait, cette somme converge extrêmement vite vers la somme infinie, et si vous prenez par exemple n = 7 vous êtes très proche de cette valeur. C'est que cette somme, quand n augmente, elle est très vite, très proche de sa limite, qui est donc, 1- exponentielle de -1. Donc, voilà, nous avons réussi à calculer, approximativement, la probabilité qu'au moins 1 lettre parvienne au bon destinataire, grâce à la formule d'inclusion-exclusion, et maintenant, on peut se demander : quelle est la probabilité, qu'aucune lettre n'arrive au bon destinataire? Donc on a fait le plus difficile, grâce à cette formule, puisque, effectivement, la probabilité qu'aucune lettre n'arrive au bon destinataire, c'est tout simplement la probabilité du complémentaire de E, c'est à dire 1- P(E), et en faisant attention aux signes, quand on tient compte de la formule précédente, qui est ici, en bas à droite ; si vous faites 1- ça, vous trouvez la somme de ( -1 puissance k ) / k!, de 1 jusqu'à n. Et ça tend très rapidement vers exponentielle de -1, qui est à peu près 0.368. Donc voilà, la probabilité qu'aucune lettre n'arrive au bon destinataire, c'est à peu près, avec une bonne marge d'erreur, plus qu'un tiers. Enfin, la dernière question qu'on se posait, c'était : quel est le nombre de manières de poster les lettres de telle manière qu'aucune lettre n'arrive au bon destinataire? Et en fait, par définition puisqu'on a supposé l'équiprobabilité, la probabilité justement, qu'aucune lettre n'arrive au bon destinataire, c'est tout simplement le nombre de façons qu'on a de les poster de telle sorte que cet événement arrive, divisé par le nombre total de façons de distribuer les lettres, qui est n!, donc on a dn qui est, en réarrangeant ce rapport, dn = n!. P ( E complémentaire ). Voilà, donc ça conclue la séance 3 d'exercice. Vous avez vu comment appliquer la formule d'inclusion-exclusion, cela apparaît dans de très nombreux problèmes, où il faut vraiment avoir une façon précise de calculer la probabilité d'union d'événements, et pas simplement se contenter d'une approximation.