Combinatoire et dénombrement
Dénombrement
Cardinal d'un ensemble
Rappel
On appelle cardinal d'un ensemble ayant un nombre fini d'éléments, le nombre d'éléments de cet ensemble.
Le produit cartésien
On appelle produit cartésien E \times F l'ensemble des couples (e,f) tels que e est un élément de E et f un élément de F.
Le principe multiplicatif se généralise au produit cartésien de n ensembles finis où n est un nombre entier naturel supérieur ou égal à 2.
Un restaurant propose sur sa carte 4 entrées, 5 plats de résistance et 6 desserts.
Soit :
- E l'ensemble des entrées ;
- P l'ensemble des plats ;
- D l'ensemble des desserts.
On considère les triplets de l'ensemble E \times P \times D.
Un triplet correspond à un menu dans lequel on a choisi une entrée, un plat et un dessert, dans cet ordre.
On a :
- Card(E)=4
- Card(P)=5
- Card(D)=6
Le nombre de menus possibles est égal à :
Card(E \times P \times D)=Card (E) \times Card(P) \times Card(D)=4 \times 5 \times 6=120
Définitions
Factorielle
Soit n un entier naturel.
On appelle factorielle n, notée n!, le nombre défini par :
\begin{cases} 0!=1 \cr \cr n!=n \times (n-1) \times ... \times 1 \text{ si n} \gt 0 \end{cases}
- 3!=3 \times 2 \times 1 = 6
- 5!=5 \times 4 \times 3 \times 2 \times 1 = 120
Permutation
Soient n un entier naturel non nul et E un ensemble de cardinal n.
On appelle permutation de l'ensemble E toute liste ordonnée de n éléments de E ne comportant pas de répétition.
Cela signifie que n éléments rangés dans deux ordres distincts correspondent à deux permutations distinctes.
Soit l'ensemble E=\left\{a;b;c \right\}. Les permutations de E sont les triplets :
- (a;b;c)
- (a;c;b)
- (b;a;c)
- (b;c;a)
- (c;a;b)
- (c;b;a)
Soit n un entier naturel non nul. Le nombre de permutations d'un ensemble à n éléments est n!
Combinaison
Soient n un entier naturel non nul et E un ensemble à n éléments. Soit k un entier naturel compris entre 0 et n.
Une combinaison de k éléments de E est une partie de E comportant k éléments.
Soit l'ensemble E=\left\{ K,L,M,P,R,S,T \right\}.
- \left\{ R,S,T \right\} est une combinaison de l'ensemble E à trois éléments.
- \left\{ K,L,M,P,R \right\} est une combinaison de l'ensemble E à cinq éléments.
k-uplets d'un ensemble
Soit un n un entier naturel non nul et E un ensemble à n éléments. Soit k un entier naturel compris entre 0 et n. Un k -uplets d'éléments de E est une partie de E comportant k éléments distincts et ordonnés.
Soit E=\left\{ A;B;I;M \right\}
La listes des 2-uplets de cet ensemble est :
- (A,B)
- (B,A)
- (A,I)
- (I,A)
- (A,M)
- (M,A)
- (B,I)
- (I,B)
- (B,M)
- (M,B)
- (I,M)
- (M,I)
Pour une combinaison, l'ordre n'a pas d'importance.
Ainsi \left\{ R,S,T \right\} et \left\{ T,S,R \right\} correspondent à la même combinaison de E.
Coefficients binomiaux
Coefficient binomial
Soient n un entier naturel, E un ensemble de cardinal n et k un entier naturel inférieur ou égal à n.
On appelle coefficient binomial le nombre lu « k parmi n », noté \begin{pmatrix} n \cr\cr k \end{pmatrix}, donnant le nombre de combinaisons de k éléments de E , c'est-à-dire le nombre de sous-ensembles de E ayant k éléments.
Ici, l'ordre des éléments n'a pas d'importance et les éléments ne se répètent pas.
Soit l'ensemble E=\left\{ 0;1;2;3;4;5 \right\}.
Les combinaisons de 5 éléments de E sont :
- \left\{1;2;3;4;5 \right\}
- \left\{ 0;2;3;4;5 \right\}
- \left\{ 0;1;3;4;5\right\}
- \left\{ 0;1;2;4;5 \right\}
- \left\{ 0;1;2;3;5 \right\}
- \left\{ 0;1;2;3;4 \right\}
Soient n un entier naturel et k un entier naturel inférieur ou égal à n. Le coefficient binomial \begin{pmatrix} n \cr\cr k \end{pmatrix} peut se calculer de la façon suivante :
\begin{pmatrix} n \cr\cr k \end{pmatrix}=\dfrac{n!}{k!(n-k)!}
Dans l'exemple précédent, le nombre de combinaisons de 4 éléments de E est égal à :
\begin{pmatrix} n \cr\cr k \end{pmatrix}=\dfrac{n!}{k!(n-k)!} avec n=6 et k=5
On obtient :
\begin{pmatrix} 6 \cr\cr 5 \end{pmatrix}=\dfrac{6!}{5!(6-5)!}=\dfrac{6!}{5!(1)!}=6
Soit n un nombre entier naturel.
On a :
- \begin{pmatrix} n \cr\cr 0 \end{pmatrix}=1
- \begin{pmatrix} n \cr\cr 1 \end{pmatrix}=n
- \begin{pmatrix} n \cr\cr 2 \end{pmatrix}=\dfrac{n(n-1)}{2}
- \begin{pmatrix} n \cr\cr n \end{pmatrix}=1
Soient n un entier naturel et k un entier naturel inférieur ou égal à n. Alors on a :
\begin{pmatrix} n \cr\cr k \end{pmatrix}=\begin{pmatrix} n \cr\cr n-k \end{pmatrix}
Soient n un entier naturel et k un entier naturel inférieur ou égal à (n-1). Alors on a :
\begin{pmatrix} n \cr\cr k \end{pmatrix}+\begin{pmatrix} n \cr\cr k+1 \end{pmatrix}=\begin{pmatrix} n+1 \cr\cr k+1 \end{pmatrix}
Calculs de nombre d'éléments
Parties d'un ensemble à n éléments
Nombre des parties d'un ensemble à n éléments
Soit n un entier naturel non nul.
Soit E un ensemble de cardinal n.
Le nombre de parties de E, c'est-à-dire le nombre de sous-ensembles de E est :
\begin{pmatrix} n \cr\cr 0 \end{pmatrix}+\begin{pmatrix} n \cr\cr 1 \end{pmatrix}+...+\begin{pmatrix} n \cr\cr n \end{pmatrix}=2^n
Soit l'ensemble E=\left\{ a;b;c \right\}.
Le nombre de parties de E est égal à :
2^3=8
Les sous-ensembles de E sont :
- l'ensemble vide : \varnothing
- ceux à 1 élément : \left\{ a \right\}, \left\{ b \right\}, \left\{ c \right\}
-
ceux à 2 éléments : \left\{ a;b \right\}, \left\{ a;c \right\}, \left\{ b;c \right\}
-
celui à 3 éléments : \left\{ a;b;c \right\}
Les ensembles suivants sont en lien. Ils sont de même cardinal : 2^n.
La loi binomiale
Succession d'épreuves indépendantes
Univers d'une succession d'épreuves indépendantes
Soient E_1, E_2, ..., E_n une succession d'épreuves indépendants d'univers respectifs \Omega_1, \Omega_2, ..., \Omega_n.
L'univers des issues de cette succession d'épreuves est le produit cartésien \Omega_1 \times \Omega_2 \times ... \times \Omega_n, c'est-à-dire l'ensemble des n-uplets \{i_1,i_2,...,i_n}\.
où chaque issue \{i_k\} est une issue de l'univers \Omega_k.
On considère les deux expériences aléatoires successives suivantes :
E_1 : lancer d'un dé tétraédrique dont les faces sont numérotées de 1 à 4.
E_2 : lancer d'une pièce de monnaie.
- Ces deux épreuves sont indépendantes.
- \Omega_1=\left\{ 1;2;3;4 \right\}
- \Omega_2=\left\{ pile;face \right\}
L'univers des issues de cette succession de deux épreuves est le produit cartésien \Omega_1 \times \Omega_2=\left\{ 1;2;3;4 \right\} \times \left\{ pile;face \right\}.
On peut représenter les différentes issues possibles à l'aide de l'arbre suivant :
Soient E_1, E_2, ..., E_n une succession d'épreuves indépendantes d'univers respectifs \Omega_1, \Omega_2, ..., \Omega_n. Soit \Omega=\Omega_1 \times \Omega_2 \times ... \times \Omega_n. Soit A=\{i_1,i_2,...,i_n}\ un évènement élémentaire de \Omega. Alors :
P(A)=P(\{i_1\}) \times ... \times P(\{i_n\})
On considère les deux expériences aléatoires successives suivantes :
E_1 : lancer d'un dé cubique qui a 2 faces vertes et 4 faces bleues.
E_2 : lancer d'une pièce de monnaie.
- Ces deux épreuves sont indépendantes.
- \Omega_1=\left\{ vert;bleu \right\}
- \Omega_2=\left\{ pile;face \right\}
L'univers des issues de cette succession de deux épreuves est le produit cartésien \Omega_1 \times \Omega_2=\left\{ vert;bleu \right\} \times \left\{ pile;face \right\}.
On peut représenter les différentes issues possibles à l'aide de l'arbre suivant :
La probabilité de l'événement \left\{ bleu;face \right\} est égale à :
P\left( \left\{ bleu \right\} \right) \times P\left( \left\{ face \right\} \right)\\=\dfrac{2}{3} \times \dfrac{1}{2}\\=\dfrac{1}{3}
Loi de Bernoulli
Épreuve de Bernoulli
Soit p un réel compris entre 0 et 1.
On appelle épreuve de Bernoulli de paramètre p toute expérience aléatoire ne comptant que deux issues, l'une nommée « succès », l'autre « échec », telle que la probabilité que le « succès » se réalise est p.
Une urne contient :
- 3 boules jaunes
- 2 boules vertes
- 1 boule bleue
On prend une boule au hasard dans cette urne.
On gagne si la boule obtenue est bleue.
La probabilité de gagner est égale à \dfrac{1}{6}.
Il s'agit d'une épreuve de Bernoulli de paramètre \dfrac{1}{6}.
Loi de Bernoulli
Soit p un réel compris entre 0 et 1.
On dit qu'une variable aléatoire X suit la loi de Bernoulli de paramètre p si :
- Les valeurs prises par X sont 0 et 1.
- P(X=1)=p
On note X → B(p).
Une urne contient 4 boules noires et 6 boules blanches.
On prend une boule hasard dans cette urne. On gagne si la boule obtenue est noire.
La probabilité de gagner est égale à \dfrac{2}{5}.
On considère la variable aléatoire X qui prend la valeur 1 si on obtient une boule noire et 0 sinon.
X suit une loi de Bernoulli de paramètre \dfrac{2}{5}.
Loi binomiale
Schéma de Bernoulli
Soit p un nombre réel compris entre 0 et 1.
On appelle schéma de Bernoulli de paramètres (n;p) une succession de n épreuves de Bernoulli indépendantes et identiques de paramètre p.
On considère l'épreuve de Bernoulli consistant à lancer un dé tétraédrique équilibré dont les faces sont numérotées de 1 à 4.
On décide que le succès correspond à l'obtention d'un 3.
On a :
p=\dfrac{1}{4}
Si on répète 100 fois cette épreuve de façon indépendante, on obtient un schéma de Bernoulli de paramètres \left(100; \dfrac{1}{4} \right) .
Loi binomiale
Soient n un entier naturel non nul et p un réel compris entre 0 et 1.
Soit X la variable aléatoire comptant le nombre de succès dans un schéma de Bernoulli de paramètres (n,p).
On dit que X suit la loi binomiale de paramètres n et p.
On note X → B(n,p).
On considère l'épreuve de Bernoulli consistant à lancer un dé cubique équilibré dont les faces sont numérotées de 1 à 6.
On décide que le succès correspond à l'obtention d'un 5.
On a : p=\dfrac{1}{6}.
Si on répète 100 fois cette épreuve de façon indépendante, on obtient un schéma de Bernoulli de paramètres \left(100; \dfrac{1}{6} \right) .
La variable aléatoire X qui compte le nombre de succès obtenus lors de cette succession de 100 épreuves de Bernoulli suit la loi binomiale de paramètres \left(100; \dfrac{1}{6} \right).
Soient n un entier naturel non nul et p un réel compris entre 0 et 1. Soit X une variable aléatoire suivant la loi B(n,p). Alors, pour tout k compris entre 0 et n, on a :
P(X=k)=\begin{pmatrix} n \cr\cr p \end{pmatrix} p^k (1-p)^{n-k}
On considère l'épreuve de Bernoulli consistant à lancer une pièce.
On décide que le succès correspond à l'obtention d'un « pile ».
On a : p=\dfrac{1}{2}.
Si on répète 30 fois cette épreuve de façon indépendante, on obtient un schéma de Bernoulli de paramètres \left(30; \dfrac{1}{2} \right) .
La variable aléatoire X qui compte le nombre de succès obtenus lors de cette succession de 30 épreuves de Bernoulli suit la loi binomiale de paramètres \left(30; \dfrac{1}{2} \right).
La probabilité d'obtenir 10 fois « pile » lors de ces 30 lancers est égale à :
P(X=10)=\begin{pmatrix} 30 \cr\cr 10 \end{pmatrix} \times 0{,}5^{10} \times (1-0{,}5)^{30-10}\\=30045015\times 0{,}5^{10}\times 0{,}5^{20}\\\approx0{,}028
Soient n un entier naturel non nul et p un réel entre 0 et 1.
Soit X une variable aléatoire suivant la loi binomiale de paramètres n et p.
Si l'on représente un diagramme en bâtons constitué en abscisses du nombre de succès possibles et en ordonnées de la probabilité correspondante, on obtient ce type de graphique :
Les variables aléatoires
Opérations sur les variables aléatoires
Somme de deux variables aléatoires
Soient X et Y deux variables aléatoires définies sur un même univers \Omega.
La variable aléatoire Z définie sur \Omega par Z(\omega)=X(\omega)+Y(\omega) pour tout élément \omega \in \Omega est appelée somme des variables aléatoires X et Y.
On la note X+Y.
On lance deux dés cubiques équilibrés dont les faces sont numérotées de 1 à 6.
Soient :
- X la variable aléatoire donnant le nombre obtenu avec le premier dé ;
- Y la variable aléatoire donnant le nombre obtenu avec le second dé.
La variable aléatoire X+Y donne la somme des nombres obtenus par les deux dés.
Linéarité de l'espérance
Soient X et Y deux variables aléatoires définies sur l'univers d'une expérience aléatoire et soit a un réel non nul.
On a alors :
- E(X+Y)=E(X)+E(Y)
- E(aX)=aE(X)
On lance deux dés tétraédriques équilibrés dont les faces sont numérotées de 1 à 4.
Soient :
- X la variable aléatoire donnant le nombre obtenu avec le premier dé.
- Y la variable aléatoire donnant le nombre obtenu avec le second dé.
On a :
E(X)=E(Y)=1\times \dfrac{1}{4}+2\times \dfrac{1}{4}+3\times \dfrac{1}{4}+4\times \dfrac{1}{4}=2{,}5
La variable aléatoire X+Y donne la somme des résultats obtenus avec les deux dés.
On a :
E(X+Y)=E(X)+E(Y)=2{,}5+2{,}5=5
Soient X et Y deux variables aléatoires définies sur l'univers d'une expérience aléatoire et soit a un réel non nul.
Si les variables X et Y sont indépendantes, alors on a :
V(X+Y)=V(X)+V(Y)
Soit X une variable aléatoire sur \Omega et a un réel.
On a :
V(aX)=a^2V(X)
Cas particulier de la loi binomiale
Soit n un entier naturel non nul et p un réel compris entre 0 et 1.
Soit X une variable aléatoire de loi B(n,p).
On a alors :
- E(X)=np
- V(X)=np(1-p)
- \sigma(X)=\sqrt{np(1-p)}
On lance 50 fois un dé cubique dont les faces sont numérotées de 1 à 6.
On décide que le succès correspond à l'obtention d'un 2.
Il s'agit alors d'une succession de 50 épreuves de Bernoulli indépendantes dont le succès « obtenir un 2 » a une probabilité de \dfrac{1}{6}.
Soit X la variable aléatoire donnant le nombre de 2 obtenus lors de ces 50 lancers.
X suit une loi binomiale de paramètres \left( 50;\dfrac{1}{6} \right).
On a alors, avec n=50 et p=\dfrac{1}{6} :
- E(X)=np=50 \times \dfrac{1}{6}=\dfrac{25}{3}
- V(X)=np(1-p)=50 \times \dfrac{1}{6} \times (1-\dfrac{1}{6})=\dfrac{125}{18}
- \sigma(X)=\sqrt{np(1-p)}=\sqrt{\dfrac{125}{18}}=\dfrac{5}{3}\sqrt{\dfrac{5}{2}}
Échantillons d'une loi de probabilité
On étudie une variable aléatoire X associée à une expérience aléatoire et qui suit une certaine loi de probabilité. On répète cette expérience plusieurs fois.
On construit alors des échantillons de résultats obtenus avec cette variable aléatoire.
On s'intéresse alors à :
- S_n la somme des échantillons
- M_n la moyenne des échantillons
Échantillon d'une loi de probabilité
Soit n un entier naturel non nul et soit une loi de probabilité.
On appelle échantillon de taille n de cette loi de probabilité toute liste (X_1,X_2,...,X_n) de n variables aléatoires indépendantes et identiques suivant toutes cette loi de probabilité.
On joue à pile ou face une fois par jour pendant une semaine.
Chaque jour, le jeu consiste en lacer 100 fois la pièce et à noter le nombre de "piles" obtenus.
En notant X_i la variable aléatoire donnant le nombre de « pile » obtenus le ième jour, toutes les variables aléatoires X_i sont indépendantes et suivent la loi B\left( 100;\dfrac{1}{2} \right).
La liste (X_1;X_2;X_3;X_4;X_5;X_6;X_7) est donc un échantillon de taille 7 de cette loi de probabilité.
Soient un entier naturel non nul n et (X_1;X_2;...;X_n) un échantillon de taille n d'une loi de probabilité.
Soient les variables aléatoires :
- S_n=X_1+X_2+...+X_n, appelée "somme des échantillons".
- M_n=\dfrac{X_1+X_2+...+X_n}{n}, appelée "moyenne des échantillons".
On a alors :
- E(S_n)=n \times E(X_1)
- V(S_n)=n \times V(X_1)
- \sigma(S_n)=\sqrt n \times \sigma (X_1)
Et :
- E(M_n)=E(X_1)
- V(M_n)=\dfrac{ V(X_1)}{n}
- \sigma(M_n)=\dfrac{ \sigma(X_1)}{\sqrt n}
On reprend l'exemple précédent.
Les variables aléatoires X_i sont indépendantes et suivent la loi B\left( 100;\dfrac{1}{2} \right).
On note S la somme des X_i.
On a alors :
- E(X_1)=100 \times \dfrac{1}{2}=50
- V(X_1)=100 \times \dfrac{1}{2} \times \dfrac{1}{2} =25
- \sigma(X_1)=\sqrt{25}=5
Par conséquent, on obtient :
- E(S)=7 \times E(X_1)=7 \times 50 = 350
- V(S)=7 \times V(X_1) =7 \times 25 = 175
- \sigma(S)=\sqrt7 \times \sigma(X_1) =\sqrt7 \times 5 = 5\sqrt 7
Et :
- E(M)=E(X_1)=50
- V(M)=\dfrac{V(X_1)}{7}=\dfrac{25}{7}
- \sigma(M)=\dfrac{\sigma(X_1)}{\sqrt7}=\dfrac{5}{\sqrt7}
La loi des grands nombres
L'inégalité de Bienaymé-Tchebychev
L'écart-type \sigma d'une variable aléatoire X est une mesure de dispersion correspondant à un écart moyen entre les valeurs prises par X et son espérance \mu.
On peut se questionner sur la probabilité que la variable X prenne des valeurs plus ou moins éloignées de son espérance et mesurer cet éloignement avec l'écart-type.
Soit X une variable aléatoire réelle, d'espérance \mu et de variance V.
Pour tout réel \delta \gt 0, on a :
P(|X-\mu| \geqslant \delta) \leqslant \dfrac{V}{\delta ^2}
Cette égalité est également appelée inégalité de Bienaymé-Tchebychev.
En choisissant \delta=n \sigma dans l'inégalité de Bienaymé-Tchebychev, on obtient :
P(|X-\mu| \geqslant n\sigma) \leqslant \dfrac{1}{n^2}
Ainsi on obtient une information sur la probabilité que l'écart entre X et son espérance dépasse un certain de nombre de fois l'écart-type.
L'inégalité de concentration
On peut majorer l'écart entre une variable aléatoire et son espérance dans le cas où l'on répète plusieurs fois la même épreuve et où l'on calcule la moyenne des résultats obtenus.
L'inégalité de concentration
Soit n un entier naturel non nul.
Soient une loi de probabilité et (X_1;X_2;...;X_n) un échantillon de cette loi constitué de variables aléatoires d'espérance \mu et de variance V.
Soit M_n=\dfrac{X_1+X_2+...+X_n}{n} la variable aléatoire moyenne.
Alors pour tout réel \delta \gt 0, on a :
P(|M_n-\mu| \geqslant \delta) \leqslant \dfrac{V}{n \delta^2}
En choisissant \delta= m \sigma avec m entier naturel non nul dans l'inégalité de concentration, on obtient :
P(|M_n-\mu| \geqslant m\sigma) \leqslant \dfrac{1}{n m^2}
Ainsi, plus la taille de l'échantillon est grand, plus la probabilité que l'écart entre M_n et \mu dépasse un certain nombre de fois \sigma est faible.
L'inégalité précédente permet de rechercher la taille n d'un échantillon pour majorer la probabilité que l'écart à l'espérance dépasse une valeur donnée.
La loi des grands nombres
On étudie ensuite l'écart entre M_n et \mu lorsque la taille de l'échantillon devient très grande.
Loi (faible) des grands nombres
Soit n un entier naturel non nul. Soient une loi de probabilité et (X_1;X_2;...;X_n) un échantillon de cette loi constitué de variables aléatoires d'espérance \mu et de variance V.
Soit M_n=\dfrac{X_1+X_2+...+X_n}{n} la variable aléatoire moyenne. Alors pour tout réel \delta \gt 0, on a :
\lim\limits_{n \to +\infty} P(|M_n-\mu| \geqslant \delta)=0
Autrement dit, plus n est grand, plus la probabilité que la variable aléatoire M_n prenne des valeurs « éloignées » de l'espérance est faible.