Fiche de révision : Combinatoire et probabilités

📋 Plan du Cours

1. Cardinalité et opérations sur les ensembles
2. Arrangements, permutations et combinaisons
3. Identités et coefficients binomiaux
4. Coefficients multinomiaux
5. Expériences aléatoires et événements
6. Événements d’un lancer de dé
7. Lois de probabilité et événements
8. Distributions usuelles
9. Probabilités conditionnelles et Bayes
10. Variables aléatoires et espérance
11. Variance et écart-type
12. Covariance des variables aléatoires
13. Inégalité de Bienaymé-Tchebychev
14. Modèle des boules et urnes
15. Charges et urnes vides

📖 1. Cardinalité et opérations sur les ensembles

🔑 Notions clés & Définitions

• Cardinal d’un ensemble : Nombre d’éléments de E.
• Complémentaire : Le complémentaire de A dans E, noté A, est l’ensemble des éléments de E qui n’appartiennent pas à A.
• Partition : Une partition d’un ensemble fini E est une famille de sous-ensembles deux à deux disjoints dont la réunion est E.

★ À maîtriser

📐 Formule - Si {A₁, …, Aₙ} est une partition de E, alors $\operatorname{Card}(E)=\sum_{i=1}^{n}\operatorname{Card}(A_i)$.

📐 Formule - Pour deux parties A et B de E, $\operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)-\operatorname{Card}(A\cap B)$.

Compléments

• L’ensemble {0, 1, 3, 4, 5, 8, 9} a pour cardinal 7.

• Les entiers premiers inférieurs à 30 sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29 ; leur cardinal est 10.

📐 Formule - Si A et B sont disjoints, alors $\operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)$.

📐 Formule - Le cardinal du complémentaire de A dans E vérifie $\operatorname{Card}(A)=\operatorname{Card}(E)-\operatorname{Card}(A)$.

📖 2. Arrangements, permutations et combinaisons

🔑 Notions clés & Définitions

• Arrangement : Suite ordonnée de k éléments distincts de E.
• Permutation : Arrangement de taille n.
• Combinaison : Une combinaison de taille k d’un ensemble à n éléments est un sous-ensemble de k éléments distincts, sans ordre.

★ À maîtriser

📐 Formule - Le nombre d’arrangements de taille k parmi n éléments est $A_n^k=\frac{n!}{(n-k)!}$.

📐 Formule - Le nombre de permutations d’un ensemble à n éléments est $P_n=A_n^n=n!$.

📐 Formule - Le nombre de combinaisons de taille k parmi n éléments est $C_n^k=\frac{A_n^k}{k!}=\frac{n!}{k!(n-k)!}$.

Compléments

• Avec 8 coureurs, le nombre de podiums ordonnés de trois places est $A_8^3=8\times7\times6=336$.

• L’attribution de quatre cadeaux distincts à quatre personnes, un cadeau par personne, peut se faire de $4!=24$ manières.

• Le choix de trois coureurs parmi huit pour un podium indifférencié donne $C_8^3=56$ combinaisons.

💡 Astuce mémo

Arrangement : l’ordre compte ; combinaison : l’ordre ne compte pas.

📖 3. Identités et coefficients binomiaux

🔑 Notions clés & Définitions

• Coefficient binomial : Les nombres C_n^k sont les coefficients binomiaux qui apparaissent dans le développement de $(a+b)^n=\sum_{k=0}^{n}C_n^k a^{n-k}b^k$.

★ À maîtriser

📐 Formule - La relation de Pascal est $C_{n+1}^k=C_n^k+C_n^{k-1}$.

Compléments

• Le développement de $(a+b)^5$ est $a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5$.

• Dans le développement de $(a+b)^5$, le coefficient 10 de $a^3b^2$ est égal à $C_5^2$, car il correspond au choix de deux facteurs b parmi les cinq facteurs.

📐 Formule - Pour n supérieur ou égal à 1, $C_n^0=C_n^n=1$.

📐 Formule - La symétrie des coefficients binomiaux s’écrit $C_n^k=C_n^{n-k}$.

📐 Formule - La somme alternée des coefficients binomiaux vérifie $\sum_{k=0}^{n}(-1)^k C_n^k=0$ pour n supérieur ou égal à 1.

📐 Formule - La somme des coefficients binomiaux d’ordre n vérifie $\sum_{k=0}^{n}C_n^k=2^n$.

📐 Formule - La convolution de Vandermonde s’écrit $C_{n+m}^k=\sum_{i=0}^{k}C_n^iC_m^{k-i}$ lorsque n et m sont supérieurs ou égaux à k.

• Dans le triangle de Pascal, la ligne n et la colonne k contiennent le coefficient binomial C_n^k.

• Le triangle de Pascal permet de calculer les coefficients binomiaux de proche en proche à partir des bords égaux à 1 et de la relation de Pascal.

📖 4. Coefficients multinomiaux

🔑 Notions clés & Définitions

• Coefficient multinomial : Les nombres $\frac{n!}{n_1!\cdots n_k!}$, pour n₁ + … + nₖ = n, sont appelés coefficients multinomiaux et interviennent dans le développement de $(a_1+\cdots+a_k)^n$.

★ À maîtriser

📐 Formule - Le nombre de permutations de n objets répartis en k groupes indistinguables de tailles n₁, …, nₖ est $\frac{n!}{n_1!\cdots n_k!}$.

Compléments

• Le coefficient multinomial compte aussi les façons de ranger n objets dans k boîtes lorsque la boîte i contient nᵢ objets.

• Pour placer les 32 pièces d’échecs sur 64 cases, le nombre de configurations données par le cours est $\frac{64!}{8!\,8!\,(2!)^6\,32!}$.

📖 5. Expériences aléatoires et événements

🔑 Notions clés & Définitions

• Expérience aléatoire : Expérience dont le résultat n’est pas connu à l’avance.
• Univers des possibles : L’univers des possibles, ou espace de probabilités, est l’ensemble de tous les résultats possibles d’une expérience aléatoire.
• Événement : Partie de l’univers des possibles E.
• Événement élémentaire : Un événement élémentaire contient un unique élément de E.
• Événements incompatibles : Deux événements sont incompatibles s’ils ne peuvent pas être réalisés simultanément, ce qui correspond à deux parties disjointes de E.
• Événement contraire : L’événement contraire de A est le complémentaire de A dans E.

📝 Points essentiels

• Les situations étudiées dans cette partie ont un univers des possibles fini.

• L’univers E est l’événement certain et l’ensemble vide est l’événement impossible.

📌 Un événement A est réalisé si le résultat élémentaire de l’expérience appartient à A.

• Pour un lancer de dé, l’univers des possibles est E={1,2,3,4,5,6} et l’événement « obtenir un nombre pair » est A={2,4,6}.

📖 6. Événements d’un lancer de dé

🔑 Notions clés & Définitions

• Événement élémentaire : Un événement élémentaire ne contient qu’une seule issue ; pour un lancer de dé, obtenir 5 correspond à $\{5\}$.

★ À maîtriser

• Pour un lancer de dé, l’événement certain est $\{1{,}2{,}3{,}4{,}5{,}6\}$ et l’événement impossible est $\varnothing$.

Compléments

• Pour un lancer de dé, l’univers des possibles est $E=\{1{,}2{,}3{,}4{,}5{,}6\}$ et l’événement « obtenir une valeur paire » est $\{2{,}4{,}6\}$.

• Pour le dé dont l’univers est $\{1{,}2{,}3{,}4{,}5{,}6\}$, le contraire de l’événement $\{4{,}5\}$ est $\{1{,}2{,}3{,}6\}$.

📌 Les événements $\{4{,}5\}$ et $\{2{,}6\}$ sont incompatibles, car ils n’ont aucune issue en commun.

📖 7. Lois de probabilité et événements

🔑 Notions clés & Définitions

• Distribution de probabilité : Une distribution de probabilité sur un ensemble fini $E=\{e_1,\ldots,e_n\}$ est une fonction $p:E\to\mathbb{R}$ telle que chaque $p(e_k)$ est compris entre 0 et 1 et que la somme des probabilités des issues vaut 1.
• Fonction de probabilité : Étant donnée une distribution $p$ sur $E$, la fonction de probabilité d’un événement $A\subseteq E$ est $P(A)=\sum_{e\in A}p(e)$.

★ À maîtriser

📐 Formule - Pour deux événements $A_1$ et $A_2$, $P(A_1\cup A_2)=P(A_1)+P(A_2)-P(A_1\cap A_2)$.

Compléments

📐 Formule - Pour tout événement $A$, $0\leq P(A)\leq 1$.

📐 Formule - Pour tout événement $A$, la probabilité de son contraire vérifie $P(\overline{A})=1-P(A)$.

📖 8. Distributions usuelles

🔑 Notions clés & Définitions

• Distribution uniforme : Une distribution uniforme attribue la même probabilité à chaque issue élémentaire.
• Expérience de Bernoulli : Une expérience de Bernoulli est une expérience aléatoire à deux issues, souvent notées 0 et 1, correspondant respectivement à l’échec et au succès lorsque ces notions s’appliquent.
• Loi de Bernoulli : La loi de Bernoulli de paramètre $p\in[0{,}1]$ est définie sur $\{0{,}1\}$ par $p(1)=p$ et $p(0)=1-p$.
• Loi binomiale : La loi binomiale de paramètres $p\in[0{,}1]$ et $n\in\mathbb{N}^*$ donne, pour chaque $k\in\{0,\ldots,n\}$, la probabilité d’obtenir $k$ succès lors de $n$ expériences de Bernoulli indépendantes de paramètre $p$.

★ À maîtriser

📐 Formule - Dans une distribution uniforme sur $E$, chaque issue a la probabilité $p(e)=\frac{1}{\operatorname{Card}(E)}$ et tout événement $A\subseteq E$ a la probabilité $P(A)=\frac{\operatorname{Card}(A)}{\operatorname{Card}(E)}$.

📐 Formule - Pour une loi binomiale de paramètres $n$ et $p$, $P(X=k)=\binom{n}{k}p^k(1-p)^{n-k}$ pour $k\in\{0,\ldots,n\}$.

Compléments

• Au loto, les tirages de 6 numéros parmi 49 sont au nombre de 13 983 816 et la probabilité qu’une grille donnée gagne le gros lot est $\frac{1}{13\,983\,816}$.

• Pour 10 alcootests avec une probabilité individuelle de résultat positif de 0,2, la probabilité d’obtenir exactement 3 résultats positifs est $\binom{10}{3}(0{,}2)^3(0{,}8)^7\approx 0{,}20$.

📖 9. Probabilités conditionnelles et Bayes

🔑 Notions clés & Définitions

• Probabilité conditionnelle : Pour deux événements $A$ et $B$ avec $P(B)>0$, la probabilité de $A$ sachant $B$ est $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$.
• Événements indépendants : Deux événements $A$ et $B$ sont indépendants si et seulement si $P(A\cap B)=P(A)P(B)$.

★ À maîtriser

📐 Formule - Si $\{A_i\}_{i\in I}$ forme une partition de $E$, alors $P(B)=\sum_{i\in I}P(B\mid A_i)P(A_i)$.

📐 Formule - Si $P(A)>0$ et $P(B)>0$, le théorème de Bayes donne $P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}$.

Compléments

📌 $P(A)$ est la probabilité a priori de $A$, tandis que $P(A\mid B)$ est sa probabilité a posteriori après observation de $B$.

• Si $P(A)>0$, la fonction définie par $p_A(e)=P(e\mid A)$ est une distribution de probabilité sur $E$.

• Si $A$ et $B$ sont indépendants et si les conditionnelles sont définies, alors $P(A\mid B)=P(A)$ et $P(B\mid A)=P(B)$.

📐 Formule - Si $\{A_i\}_{i\in I}$ forme une partition de $E$ et si la probabilité conditionnelle est définie, alors $P(A_i\mid B)=\frac{P(B\mid A_i)P(A_i)}{\sum_{j\in I}P(B\mid A_j)P(A_j)}$.

• Dans une promotion de 132 étudiants, 45 sont enfants uniques, 25 jouent de la guitare et 18 sont à la fois enfants uniques et guitaristes ; la probabilité qu’un guitariste rencontré soit enfant unique est $\frac{18}{25}\approx 0{,}72$.

• Dans l’exemple des tailles, avec $P(H)=P(F)=0{,}5$, $P(G\mid H)=0{,}60$ et $P(G\mid F)=0{,}06$, les probabilités postérieures sont $P(H\mid G)\approx0{,}91$ et $P(F\mid G)\approx0{,}09$.

📖 10. Variables aléatoires et espérance

🔑 Notions clés & Définitions

• Variable aléatoire : Une variable aléatoire sur $E$ est une fonction $X:E\to\mathbb{R}$ qui associe une valeur réelle à chaque issue élémentaire.
• Espérance mathématique : L’espérance mathématique d’une variable aléatoire $X$ définie sur un ensemble $E$ muni d’une distribution $p$ est $\mathbb{E}(X)=\sum_{e\in E}p(e)X(e)$.
• Variables indépendantes : Deux variables aléatoires X et Y sont indépendantes si et seulement si, pour toutes valeurs v et w, $p(X=v\text{ et }Y=w)=p(X=v)p(Y=w)$.

★ À maîtriser

📐 Formule - L’espérance peut s’écrire comme la somme des valeurs possibles pondérées par leur probabilité : $E(X)=\sum_{v\in X(E)}v\,p(X=v)$.

📐 Formule - L’espérance est linéaire : $E(X_1+\cdots+X_n)=\sum_{i=1}^{n}E(X_i)$ et $E(aX+b)=aE(X)+b$ pour $a,b\in\mathbb{R}$.

📐 Formule - Si X suit une loi de Bernoulli de paramètre p, alors $E(X)=p$.

📐 Formule - Si Y suit une loi binomiale de paramètres n et p, alors $E(Y)=np$.

Compléments

📐 Formule - Pour une valeur $v$, $P(X=v)=P(\{e\in E:X(e)=v\})$, c’est-à-dire la probabilité de l’ensemble des issues auxquelles $X$ attribue la valeur $v$.

• Pour le jeu de dé décrit, les points associés aux faces 1 à 6 sont respectivement 10, 1, 1, −15, 1 et 10 ; ainsi, les probabilités des gains −15, 10 et 1 sont respectivement $\frac16$, $\frac26$ et $\frac36$.

📐 Formule - Si $X$ compte les succès obtenus lors de $n$ tirages indépendants d’une expérience de Bernoulli de paramètre $p$, alors $P(X=k)=\binom{n}{k}p^k(1-p)^{n-k}$.

• L’espérance mathématique d’une variable aléatoire correspond à sa valeur moyenne après un nombre important, théoriquement infini, de tirages.

• Dans le jeu de dé, les gains possibles sont −15, 1 et 10, de probabilités respectives 1/6, 3/6 et 2/6, ce qui donne une espérance d’environ 1,33 point.

📐 Formule - Si X et Y sont indépendantes, alors $E(XY)=E(X)E(Y)$.

📖 11. Variance et écart-type

🔑 Notions clés & Définitions

• Variance : La variance d’une variable aléatoire X est l’espérance du carré de son écart à sa moyenne : $V(X)=E((X-E(X))^2)$.
• Écart-type : L’écart-type d’une variable aléatoire X est la racine carrée de sa variance : $\sigma(X)=\sqrt{V(X)}$.

★ À maîtriser

📐 Formule - Pour tout réel a et b, $V(aX+b)=a^2V(X)$.

Compléments

• La variance et l’écart-type représentent la dispersion d’une variable aléatoire autour de sa valeur moyenne, et l’écart-type s’exprime dans la même unité que la variable.

• Pour un dé normal, l’espérance du nombre de points affichés est 3,5, la variance est approximativement 2,92 et l’écart-type est approximativement 1,71.

• Pour le jeu de dé, l’espérance des gains vaut environ 1,33, la variance environ 69,56 et l’écart-type environ 8,34.

📖 12. Covariance des variables aléatoires

🔑 Notions clés & Définitions

• Covariance : La covariance de deux variables aléatoires X et Y est $\operatorname{Cov}(X,Y)=E((X-E(X))(Y-E(Y)))$.

★ À maîtriser

📐 Formule - La covariance vérifie $\operatorname{Cov}(X,Y)=E(XY)-E(X)E(Y)$.

📐 Formule - La variance d’une somme vérifie $V(X+Y)=V(X)+V(Y)+2\operatorname{Cov}(X,Y)$.

Compléments

• La covariance généralise la notion de variance.

📐 Formule - Si X et Y sont indépendantes, alors $\operatorname{Cov}(X,Y)=0$.

📐 Formule - La covariance d’une variable avec elle-même est sa variance : $\operatorname{Cov}(X,X)=V(X)$.

📐 Formule - Pour tout réel a, $\operatorname{Cov}(aX,Y)=a\operatorname{Cov}(X,Y)$ et $\operatorname{Cov}(X+a,Y)=\operatorname{Cov}(X,Y)$.

📖 13. Inégalité de Bienaymé-Tchebychev

★ À maîtriser

📌 Si une variable aléatoire X a pour espérance μ et pour variance σ², alors, pour λ, $P(|X-\mu|>\lambda\sigma)\leq\frac{1}{\lambda^2}$. - Bienaymé-Tchebychev

Compléments

• Pour le poids de Hamming H₃₂ d’un entier aléatoire codé sur 32 bits, l’espérance vaut 16 et l’écart-type vaut √8, soit environ 2,83.

• Avec λ=(16−4)/√8, soit environ 4,24, l’inégalité donne pour le poids de Hamming la borne P(H₃₂≤4 ou H₃₂>28)≤1/λ², soit environ 0,056.

• Dans un exercice antérieur, la probabilité considérée pour le poids de Hamming était inférieure à 2·10⁻⁵.

📖 14. Modèle des boules et urnes

🔑 Notions clés & Définitions

• Modèle des boules et urnes : Le modèle répartit m boules dans n urnes en plaçant chaque boule indépendamment dans une urne choisie uniformément au hasard.

★ À maîtriser

📐 Formule - Dans le modèle des boules et urnes, la probabilité que deux boules données entrent en collision est $\frac{1}{n}$.

📐 Formule - Le nombre moyen de collisions entre paires de boules est $E(\text{nombre de collisions})=\frac{1}{n}\binom{m}{2}$.

Compléments

• Pour les anniversaires, on modélise les 365 dates de l’année par les urnes et les personnes par les boules ; 28 personnes donnent en moyenne environ une collision de date d’anniversaire.

📖 15. Charges et urnes vides

★ À maîtriser

📐 Formule - La probabilité qu’une urne donnée soit vide est $\left(1-\frac{1}{n}\right)^m\approx\left(\frac{1}{e}\right)^{m/n}$.

📌 Lorsque m=n, la charge maximale est majorée par $\frac{3\ln n}{\ln\ln n}$ avec une probabilité $1-\frac{1}{n}$.

📐 Formule - Lorsque m=n, la charge maximale moyenne est $E(\text{charge maximale})=\frac{\ln n}{\ln\ln n}(1+O(1))$.

Compléments

📐 Formule - Le nombre moyen d’urnes vides est $n\left(1-\frac{1}{n}\right)^m\approx n\left(\frac{1}{e}\right)^{m/n}$.

📌 La probabilité qu’une urne donnée contienne au moins k boules est difficile à calculer, mais elle est majorée par $\binom{m}{k}\left(\frac{1}{n}\right)^k$.

• Pour n=10 000, les quantités $\frac{\ln n}{\ln\ln n}$ et $\frac{3\ln n}{\ln\ln n}$ valent environ 4,15 et 12,44.