Dénombrement et conditionnement en maths sup (MPSI) : cours et méthodes

On dit que \(E\) est fini lorsque \(E = \varnothing\), ou lorsque \(E\) peut être mis en bijection avec \([\![1, n]\!]\) pour un certain \(n \geqslant 1\). Un tel \(n\) est alors unique ; on l’appelle cardinal de \(E\), noté \(\mathrm{Card}\, E\), \(|E|\) ou \(\#E\). Par convention, \(\mathrm{Card}\, \varnothing = 0\).

Soient \(A\) et \(B\) deux parties finies d’un ensemble \(E\) fini.

• Si \(A \cap B = \varnothing\), alors \(\mathrm{Card}(A \cup B) = \mathrm{Card}\, A + \mathrm{Card}\, B\).
• Le complémentaire vérifie \(\mathrm{Card}(E \setminus A) = \mathrm{Card}\, E – \mathrm{Card}\, A\).
• En général, \(\mathrm{Card}(A \cup B) = \mathrm{Card}\, A + \mathrm{Card}\, B – \mathrm{Card}(A \cap B)\).

Le premier point découle de la définition, en juxtaposant deux bijections. Ensuite, \(E\) est la réunion disjointe de \(A\) et de son complémentaire, ce qui donne le deuxième point. Enfin, \(A \cup B\) est la réunion disjointe de \(A\) et de \(B \setminus A\). Or \(B\) est la réunion disjointe de \(B \setminus A\) et de \(A \cap B\). Ainsi \(\mathrm{Card}(B \setminus A) = \mathrm{Card}\, B – \mathrm{Card}(A \cap B)\), d’où la formule.

Combien d’entiers de \([\![1, 300]\!]\) sont multiples de \(4\) ou de \(6\) ? Notons \(A\) les multiples de \(4\) et \(B\) ceux de \(6\). On a \(\mathrm{Card}\, A = 75\) et \(\mathrm{Card}\, B = 50\). Ensuite, un entier est multiple de \(4\) et de \(6\) exactement quand il est multiple de leur PPCM, qui vaut \(12\). Donc \(\mathrm{Card}(A \cap B) = 25\). Par conséquent, \(\mathrm{Card}(A \cup B) = 75 + 50 – 25 = 100\).

Si \(E\) et \(F\) sont finis, alors \(\mathrm{Card}(E \times F) = \mathrm{Card}\, E \times \mathrm{Card}\, F\). Plus généralement, \(\mathrm{Card}(E_1 \times \cdots \times E_p) = \prod_{i=1}^{p} \mathrm{Card}\, E_i\). De plus, si \(\mathrm{Card}\, E = n\), l’ensemble \(\mathcal{P}(E)\) de ses parties a pour cardinal \(2^n\).

Le produit \(E \times F\) est la réunion disjointe des ensembles \(\{x\} \times F\), pour \(x \in E\). Chacun a \(\mathrm{Card}\, F\) éléments, d’où le premier point. Une récurrence donne ensuite le cas de \(p\) facteurs. Pour les parties, écrivons \(E = \{x_1, \dots, x_n\}\). À une partie \(A\), on associe la liste \((\varepsilon_1, \dots, \varepsilon_n)\) de \(\{0, 1\}^n\), avec \(\varepsilon_i = 1\) si et seulement si \(x_i \in A\). Cette application est une bijection, donc \(\mathrm{Card}\, \mathcal{P}(E) = 2^n\).

Une \(p\)-liste de \(E\) est un élément de \(E^p\), c’est-à-dire une suite ordonnée de \(p\) éléments, avec répétitions possibles. Lorsque les \(p\) termes sont tous différents, on parle d’arrangement. Toute bijection de \(E\) dans lui-même s’appelle une permutation. Enfin, une combinaison de \(p\) éléments de \(E\) est une partie de \(E\) à \(p\) éléments.

Pour \(\mathrm{Card}\, E = n\) :

• le nombre de \(p\)-listes est \(n^p\) ;
• le nombre d’arrangements de \(p\) éléments est \(n(n – 1) \cdots (n – p + 1) = \dfrac{n!}{(n – p)!}\) si \(p \leqslant n\), et \(0\) sinon ;
• le nombre de permutations est \(n!\) ;
• le nombre de combinaisons de \(p\) éléments est \(\dbinom{n}{p} = \dfrac{n(n-1)\cdots(n-p+1)}{p!}\) si \(p \leqslant n\), et \(0\) sinon.

Les \(p\)-listes forment \(E^p\), de cardinal \(n^p\). Pour un arrangement, on a \(n\) choix pour le premier terme, puis \(n – 1\) pour le deuxième, et ainsi de suite jusqu’à \(n – p + 1\) choix pour le dernier. Une permutation est un arrangement de \(n\) éléments, d’où \(n!\). Enfin, chaque combinaison de \(p\) éléments donne exactement \(p!\) arrangements, obtenus en ordonnant ses éléments. Le nombre d’arrangements vaut donc \(p!\) fois le nombre de combinaisons.

1. Décrire précisément un résultat de l’expérience, par exemple « un podium » ou « une main de cartes ».
2. Se demander si deux résultats qui ne diffèrent que par l’ordre doivent être distingués.
3. Se demander si un même élément peut apparaître plusieurs fois.
4. En déduire le modèle : listes, arrangements ou combinaisons, puis appliquer la formule.
5. Contrôler sur un petit cas, en énumérant à la main quand c’est possible.

Neuf coureurs disputent une course. Le nombre de podiums possibles, avec or, argent et bronze, est le nombre d’arrangements \(9 \times 8 \times 7 = 504\), car l’ordre compte. En revanche, le nombre de trios qualifiés pour une finale, sans classement, vaut \(\binom{9}{3} = 84\). On retrouve \(504 = 3! \times 84\). Enfin, un code de \(4\) caractères pris parmi \(5\) symboles, avec répétitions permises, admet \(5^4 = 625\) possibilités.

Le mot RADAR contient deux R, deux A et un D. Si les cinq lettres étaient distinctes, on aurait \(5! = 120\) anagrammes. Chaque mot est obtenu \(2! \times 2! = 4\) fois, en échangeant les R entre eux et les A entre eux. Par conséquent, RADAR possède \(120 / 4 = 30\) anagrammes. Autre méthode : on choisit les \(2\) places des R parmi \(5\), puis les \(2\) places des A parmi les \(3\) restantes, soit \(\binom{5}{2}\binom{3}{2} = 10 \times 3 = 30\).

Pour \(0 \leqslant p \leqslant n\), on a la symétrie \(\binom{n}{n-p} = \binom{n}{p}\). Pour \(1 \leqslant p \leqslant n\), on a la relation de Pascal \(\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}\). Enfin, \(\sum_{p=0}^{n} \binom{n}{p} = 2^n\).

Nous raisonnons par bijection et par partition, sans calcul. D’abord, le passage au complémentaire est une bijection des parties à \(p\) éléments sur celles à \(n – p\) éléments. Ensuite, fixons \(a \in E\). Les parties à \(p\) éléments se répartissent en deux classes : celles qui contiennent \(a\), au nombre de \(\binom{n-1}{p-1}\), et les autres, au nombre de \(\binom{n-1}{p}\). Enfin, \(\mathcal{P}(E)\) est la réunion disjointe des ensembles de parties de cardinal \(p\), pour \(p\) de \(0\) à \(n\).

1. Interpréter chaque membre de l’identité comme un nombre de choix : comités, chemins, mots, couples.
2. Trouver un ensemble unique dont le cardinal se calcule de deux manières, une par membre.
3. Pour une somme, partitionner cet ensemble selon un paramètre : le plus grand élément, la position d’un objet, le nombre d’éléments d’un certain type.
4. Rédiger en nommant l’ensemble compté et la partition utilisée.

Montrons que \(p\binom{n}{p} = n\binom{n-1}{p-1}\) pour \(1 \leqslant p \leqslant n\). Comptons les couples \((C, c)\) où \(C\) est un comité de \(p\) personnes parmi \(n\) et \(c\) un capitaine choisi dans \(C\). D’une part, on choisit le comité, puis le capitaine : \(\binom{n}{p} \times p\) façons. D’autre part, on choisit d’abord le capitaine parmi \(n\), puis les \(p – 1\) autres membres parmi les \(n – 1\) personnes restantes : \(n \binom{n-1}{p-1}\) façons. Les deux nombres sont donc égaux.

Formule du binôme. Pour \(a\), \(b\) complexes et \(n \in \mathbb{N}\),
\[(a + b)^n = \sum_{p=0}^{n} \binom{n}{p} a^p b^{n-p}.\]

Développons le produit de \(n\) facteurs \((a + b)\). On obtient une somme de \(2^n\) termes : chaque terme correspond au choix, dans chaque facteur, de \(a\) ou de \(b\). Un terme vaut \(a^p b^{n-p}\) quand on a choisi \(a\) dans exactement \(p\) facteurs. Choisir ces facteurs revient à choisir une partie à \(p\) éléments de \([\![1, n]\!]\). Ainsi, le terme \(a^p b^{n-p}\) apparaît \(\binom{n}{p}\) fois.

Un univers \(\Omega\) est un ensemble fini dont les éléments représentent les issues d’une expérience. Un événement est une partie de \(\Omega\). Deux événements \(A\) et \(B\) sont incompatibles si \(A \cap B = \varnothing\). Une famille \((A_1, \dots, A_m)\) d’événements est un système complet s’ils sont deux à deux incompatibles et de réunion \(\Omega\).

Une probabilité sur \(\Omega\) est une application \(P : \mathcal{P}(\Omega) \to [0, 1]\) telle que \(P(\Omega) = 1\) et \(P(A \cup B) = P(A) + P(B)\) dès que \(A\) et \(B\) sont incompatibles. Le couple \((\Omega, P)\) est un espace probabilisé fini.

La probabilité uniforme sur \(\Omega\) est celle qui donne le même poids à chaque issue. Elle vérifie, pour tout événement \(A\),
\[P(A) = \frac{\mathrm{Card}\, A}{\mathrm{Card}\, \Omega}.\]

Soit \(B\) un événement tel que \(P(B) > 0\). La probabilité de \(A\) sachant \(B\) est
\[P_B(A) = P(A \mid B) = \frac{P(A \cap B)}{P(B)}.\]
L’application \(P_B\) est une probabilité sur \(\Omega\).

Si \(P(A_1 \cap \cdots \cap A_{m-1}) > 0\), alors
\[P(A_1 \cap \cdots \cap A_m) = P(A_1)\, P_{A_1}(A_2)\, P_{A_1 \cap A_2}(A_3) \cdots P_{A_1 \cap \cdots \cap A_{m-1}}(A_m).\]

Une urne contient \(4\) boules rouges et \(3\) bleues. On tire trois boules successivement, sans remise. Notons \(R_i\) l’événement « la \(i\)-ème boule est rouge ». Alors
\[P(R_1 \cap R_2 \cap \overline{R_3}) = \frac{4}{7} \times \frac{3}{6} \times \frac{3}{5} = \frac{36}{210} = \frac{6}{35}.\]
En effet, après deux rouges, il reste \(2\) rouges et \(3\) bleues, soit \(5\) boules.

Formule des probabilités totales. On se donne un système complet \((A_1, \dots, A_m)\) dont aucun événement n’est négligeable. Alors, quel que soit \(B\),
\[P(B) = \sum_{i=1}^{m} P(A_i)\, P_{A_i}(B).\]
Formule de Bayes. Si de plus \(P(B) > 0\), alors pour tout \(j\),
\[P_B(A_j) = \frac{P(A_j)\, P_{A_j}(B)}{\sum_{i=1}^{m} P(A_i)\, P_{A_i}(B)}.\]

Les événements \(B \cap A_i\) sont deux à deux incompatibles, et leur réunion est \(B\), car les \(A_i\) recouvrent \(\Omega\). Par additivité, \(P(B) = \sum P(B \cap A_i)\), et chaque terme vaut \(P(A_i)\, P_{A_i}(B)\). Pour Bayes, on écrit \(P_B(A_j) = P(A_j \cap B) / P(B)\), puis on remplace le numérateur par \(P(A_j)\, P_{A_j}(B)\) et le dénominateur par la formule précédente.

Un atelier fabrique des pièces sur deux machines. La machine \(M_1\) produit \(60\,\%\) des pièces, dont \(3\,\%\) sont défectueuses. La machine \(M_2\) produit le reste, avec \(5\,\%\) de défauts. Notons \(D\) l’événement « la pièce est défectueuse ». Le couple \((M_1, M_2)\) est un système complet. D’abord, \(P(D) = 0{,}6 \times 0{,}03 + 0{,}4 \times 0{,}05 = 0{,}018 + 0{,}02 = 0{,}038\). Ensuite, la formule de Bayes donne
\[P_D(M_2) = \frac{0{,}02}{0{,}038} = \frac{10}{19} \approx 0{,}53.\]
Ainsi, une pièce défectueuse vient plus souvent de \(M_2\), bien que cette machine produise moins.

Deux événements \(A\) et \(B\) sont indépendants si \(P(A \cap B) = P(A)\, P(B)\). Des événements \(A_1, \dots, A_m\) sont mutuellement indépendants si, pour toute partie \(I\) non vide de \([\![1, m]\!]\),
\[\prod_{i \in I} P(A_i) = P\Big(\bigcap_{i \in I} A_i\Big).\]

L’indépendance mutuelle est plus forte que l’indépendance deux à deux. Prenons un dé équilibré à quatre faces numérotées de \(1\) à \(4\), et posons \(A = \{1, 2\}\), \(B = \{1, 3\}\), \(C = \{1, 4\}\). Chaque événement a pour probabilité \(1/2\). Chaque intersection de deux d’entre eux vaut \(\{1\}\), de probabilité \(1/4 = (1/2)^2\). Les événements sont donc indépendants deux à deux. Cependant, la probabilité de \(A \cap B \cap C\) vaut \(\frac{1}{4}\), et non \(\frac{1}{8}\) : ils ne sont pas mutuellement indépendants.

On tire \(3\) cartes parmi \(10\), dont \(4\) cartes « atout ». Calculons la probabilité d’obtenir exactement \(2\) atouts. Avec les combinaisons, on obtient \(\binom{4}{2}\binom{6}{1} / \binom{10}{3} = 36/120 = 3/10\). Avec les arrangements, on choisit d’abord la position de la carte non atout parmi \(3\), puis on compte \(3 \times (4 \times 3 \times 6) / (10 \times 9 \times 8) = 216/720 = 3/10\). Le résultat est bien le même.

Pour rédiger un exercice de probabilités, on suit toujours le même plan. D’abord, on nomme les événements utiles par des lettres. Ensuite, on traduit chaque donnée de l’énoncé en une probabilité ou une probabilité conditionnelle. Puis on cite le système complet utilisé et la formule appliquée. Enfin, on conclut par une phrase qui répond à la question posée.

• S’exercer : exercices corrigés de maths sup (MPSI) sur dénombrement et conditionnement
• Bases utiles : Calculer avec Σ et Π : télescopage et binôme, Ensembles, injections, surjections et relations
• Chapitre d’avant : Sommation par paquets et familles sommables
• Chapitre d’après : Variables aléatoires finies, espérance et variance
• Vérifier ses acquis : QCM de maths sup (MPSI) sur dénombrement et conditionnement
• Contrôle corrigé en temps limité : Urnes, dénombrement et formule de Bayes : contrôle de maths en MPSI
• Tous les chapitres : le sommaire de maths sup (MPSI)
• Après le bac : les maths post-bac, de la MPSI à la L3