Chap 1

PROBABILITES ET STATISTIQUE I&II CHAPITRE I. COMBINATOIRE ELEMENTAIRE

I.1.

Rappel des notations de la théorie des ensemble

I.1.a. Ensembles et sous-ensembles Un ensemble E est une collection d'objets appelés éléments. Si x est un élément de E on dit que x appartient à E ou que E contient x, et on note x ∈ E. Si x n’est pas un élément de E on note x ∉ E. L’ensemble E peut avoir un nombre fini ou infini d’éléments. Dans le dernier cas E peut être dénombrable (par exemple E = Z, l’ensemble des entiers) ou pas dénombrable (par exemple E = R, l’ensemble des nombres réels). L’ensemble vide, noté { }ou ∅, n’a aucun élément. L’ensemble A est un sous-ensemble (on dit aussi partie) de l’ensemble de E si chaque élément de A est un élément de E. On note : A ⊆ E. Si A ⊆ B et B ⊆ A, A et B contiennent les mêmes éléments. On le note A = B. I.1.b. Diagrammes (dits de Venn)

A ⋅x

Ε x∈A⊆E

1

I.1.c. Cardinal d’un ensemble fini Un ensemble E est fini s’il possède un nombre fini d’éléments. On appelle cardinal de E, le nombre de ces éléments qu’on note card E (ou #E ou |E|). Propriétés évidentes : 1) Si E = ∅ alors card E = 0. 2) Si A ⊆ E alors card A ≤ card E. I.1.d. Opérations booléennes Si A ⊆ E et si B ⊆ E, on définit la réunion de A et B comme l’ensemble des éléments de E qui sont éléments de A ou B : A ∪ B = {x∈E, x∈A ou x∈B }. Evidemment la réunion de A et B contient au plus tous les éléments de A et tous de B (si A et B n’ont aucun élément en commun), ce qui donne pour des ensembles finis l’inégalité: card(A ∪ B) ≤ card(A) + card(B). On définit ainsi l’intersection de A et B comme l’ensemble des éléments de E qui sont éléments de A et B : A ∩ B = {x∈E, x∈A et x∈B }. Le principe d’exclusion-inclusion nous fournit une relation pour le cardinal de A , B, A ∩ B, et A ∪ B : card(A ∪ B) + card(A ∩ B) = card(A) + card(B). On définit le complémentaire de A comme l’ensemble des éléments de E qui ne sont pas des éléments de A : Ac = {x∈E, x∉A}. Evidemment on a la relation card(A) + card(Ac) = card(E).

La différence de A et B est définie comme l’ensemble des éléments de E qui sont éléments de A et qui ne sont pas éléments de B : A \ B = {x∈E, x∈A et x∉B } = A ∩ Bc. La différence symétrique de A et B est définie par : A ∆ B = (A \ B) ∪ (B \ A).

2

I.1.e. Suites de sous-ensembles Soient A1, A2,…, Ai, Ai+1,… des sous-ensembles d’un ensemble E. On peut généraliser les notions de réunion et d’intersection en définissant : •

∞

∪A

i

comme le sous-ensemble de E constitué des éléments de E qui

i =1

appartiennent à au moins un des sous-ensembles Ai •

∞

∩ Ai

comme le sous-ensemble de E constitué des éléments de E qui

i =1

appartiennent à tous les sous-ensembles Ai. Définition : Les (Ai)1≤i sont disjoints deux à deux si et seulement si (en abrégé ssi), pour tout i ≠ j Ai ∩ Aj = ∅. Les (Ai)1≤i forment une partition de l’ensemble E s’ils sont ∞

disjoints deux à deux et si : ∪ Ai = E . Dans ce cas pour tout élément x de E, il existe i =1

un i et un seul i tel que x∈ Ai. I.1.f. Ensemble produit cartésien Soient E, F deux ensembles. On définit le produit cartésien de E et F par : E × F = {(x,y), x∈E et y∈F}. C’est l’ensemble des couples (x,y) ou x∈E et y∈F. Attention: Couple et paire sont des notions différentes et donc E × F ≠ F × E. De même on définit le produit cartésien pour n ensembles (Ei)1≤i≤n: E1 × …× En = {(x1,…, xn), x1∈E1,…, xn∈En}. Si Ei = E pour tout i on écrit En pour le produit cartésien . Le cardinal d’un produit cartésien : Si E et F sont des ensembles finis alors le produit cartésien E × F est un ensemble fini et card(E × F) = card(E) card(F). Dans le cas général, on a pour n ensembles finis (Ei)1≤i≤n: card(E1 × …× En) = card(E1)⋅…⋅card(En). Tableau 1: Produit cartésien E× ×F

F E

1

2

3

4

5

6

a

a1

a2

a3

a4

a5

a6

b

b1

b2

b3

b4

b5

b6

c

c1

c2

c3

c4

c5

c6

d

d1

d2

d3

d4

d5

d6 3

I.1.g. Propriétés élémentaires du complémentaire et des opérations booléennes 1) 2) 3) 4) 5) 6) 7)

I.2.

(Ac)c = A (A ∪ B)c = Ac ∩ Bc (A ∩ B)c = Ac ∪ Bc (∪i≥1 Ai)c =

∩ i≥1 Aic ∪i≥1 Aic

(∩i≥1 Ai)c = A ∩ (B ∪ C) = (A ∩ B ) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B ) ∩ (A ∪ C)

Notions de combinatoire

I.2.a. La règle de multiplication Question: Monsieur Hasard a 6 pantalons, 4 chemises, 2 vestes et 3 paires de chaussures. Combien at-il de façons de s’habiller? Réponse: Evidemment il y a 6⋅4⋅2⋅3 = 144 façons de s’habiller pour Monsieur Hasard.

Principe : Si l’on fait m expériences de suite et si (indépendamment des résultats des expériences 1,2, …, k-1) l’expérience k a nk résultats possibles alors le nombre de résultats possibles pour la suite de m expériences est n1⋅ n2⋅...⋅ nm. Formulation mathématique : (→ cardinal du produit cartésien, Ch. I.1.f) Soit Ek l’ensemble des résultats possibles de la kème expérience et card Ek = nk. Alors E1 × …× Em = {(x1,…, xm), x1∈E1,…, xm∈Em} est l'ensemble des résultats possibles pour la suite de m expériences. Question : Combien y-a-t-il de façons de répondre à un questionnaire de 15 questions? 1) Si on répond par oui/non. (réponse: 215) 2) Si on répond par oui/non/je ne saisi pas. (réponse: 315)

Formulation mathématique : Le nombre d’applications d’un ensemble à k éléments dans un ensemble à n éléments est nk. 1 2 . . .

1 2 . . .

1 2 . . .

k

n

15

questions

réponses par question 4

oui non

I.2.b. Permutations et arrangements Question: Combien y-a-t-il de façons de ranger 6 livres sur une étagère? Réponse: Par le principe de multiplication on a 6⋅5⋅4⋅3⋅2⋅1 = 6!

Formulation mathématique : Il y a n ! = n⋅(n-1)⋅…⋅2⋅1 bijections (permutations) d’un ensemble à n éléments dans un ensemble à n éléments.

1 2 . . .

1 2 . . . n

n

1à1

livre

position

Question : 12 personnes font parties d’un club de probabilistes. Combien y-a-t-il de façons de choisir : 1 président, 1 vice-président, 1 trésorier et 1 secrétaire ? Réponse: 12⋅11⋅10⋅9= 11 880.

Considérons le cas général de n membres du club et k fonctions, 0 ≤ k ≤ n. La réponse est n⋅(n-1)⋅...⋅(n-k+1) = n! / (n-k)!

Formulation mathématique : Il y a An = k

n! ( n − k )!

injections d’un ensemble à k éléments dans un ensemble à n éléments.

1 2 . . .

1 2 . . .

k

n

fonctions

membres

5

I.2.c. Combinaisons (sans répétition) Question: Il y a toujours 12 membres dans le club de probabilistes. Combien y-a-t-il de façons de constituer un comité de 4 membres ? Réponse:

⋅ ⋅9 12⋅1110 4⋅3⋅2⋅1

= 495 (l'ordre n'est pas important).

Généralisation: n membres et un comité de k , 0 ≤ k ≤ n:  n Ank n! = = Cnk =   k ! (n − k )! k !  k

Question: Combien y-a-t-il de mains de poker ? Réponse:

5 C52 .

Formulation mathématique : Il y a Cn = k

n! k !( n − k )!

sous-ensemble à k éléments dans un ensemble à n éléments

pour 0 ≤ k ≤ n.

Exemples: Cn0 = 1 Cn1 = n Cn2 = n ( n2−1) Remarquons que Cn2 est différent du nombre des paires (= Cn2+1 = des couples (= n2).

n ( n +1) 2

) et

du nombre

Le problème suivant amène également aux coefficients binomiaux : Question: Un code binaire est une suite (ou un vecteur) constituée des chiffres 0 et 1.On considère des codes binaires de longueur 12. Combien y-a-t-il des codes contenants exactement 4 fois le chiffre 1? Réponse: C412 = 495. Noter l’équivalence au problème de comité : On choisit 4 positions (membres) sur 12.

Généralisation: code binaire de longueur n contenant k fois « 1 », 0 ≤ k ≤ n: Ckn.

6

I.2.d. Propriétés des coefficients binomiaux Théorème : (Formule du binôme de Newton ):

(a + b )

n

n

= ∑ Cnk a n −k bk k =0

Exemples (a + b)0 = 1

(a + b)1 = C10 a + C11b = a + b (a + b)2 = C20 a 2 b 0 + C21a 1b1 + C20 a 0b 2 = a 2 + 2ab + b 2 (a + b)3 = C30 a 3b 0 + C31a 2 b 1 + C32 a 1b 2 + C33 a 0b 2 = a 3 + 3a 2 b + 3ab 2 + b 3 En appliquant le théorème de Newton avec a = 1 et b = x ou b = -x on obtient les deux identités suivantes:

(1 + x )

n

n

= ∑ Cnk x k k =0 n

(1 − x ) = ∑ Cnk ( −1)k x k n

k =0

Pour x=1 ceci nous donne n

2n = ∑ Cnk k =0

n

0 = ∑ ( −1) k Cnk k =0

La première identité signifie que le nombre total des sous-ensembles d’un ensemble à n éléments est 2n. Exemple :

Pour E ={a, b, c} les sous-ensembles possibles sont : ∅:

C30 = 1 sous-ensemble de cardinal 0,

{a},{b},{c}

C31 = 3 sous-ensembles de cardinal 1,

{a, b},{b, c},{a, c}

C32 = 3 sous-ensembles de cardinal 2,

{a, b, c}

C33 = 1 sous-ensemble de cardinal 3,

soit 23 = 8 sous-ensembles au total.

7

Théorème : (Triangle de Pascal ) Cnk = Cnk−−11 + Cnk−1 .

0 1 2 3 4 5 . n

0 1 1 1 1 1 1

1

2

3

4

5

1 2 3 4 5

1 3 6 10

1 4 10

1 5

1

1

.

.

.

.

.

.

k

Cnk

Représentation symétrique: 1 1 1 1 1 1

1 2

3 4

1 3

6

5

10

1 4

10

.

1 5

1 .

1

1

Théorème : (Formule de Vandermonde) k

Cmj Cnk − j = Cnk+m ∑ j =0

8

1.2.e. Coefficients multinomiaux Question : Combien y a-t-il de façons de distribuer les 52 cartes d'un jeu de bridge en 4 mains ? 13 13 13 13 52! = 53 644 737 765 488 792 839 237 440 000. C52 ⋅ C39 ⋅ C26 ⋅ C13 = 13!13!13!13!

Réponse:

Formulation mathématique : Il y a Cn 1 ⋅ Cn−2 n ⋅ … ⋅ Cn−k n −...−n n

n

n

1

1

k −1

=

n! n1 !n2 !...nk !

façons de partager un ensemble de k

cardinal n en k sous-ensembles (disjoints deux à deux) de cardinaux ni où

∑ ni = n . i =1

Théorème (formule du multinôme) :

∑

(a1 + a2 + ... + ak ) n =

( n1 ,...,nk ): n1 +...+ nk = n

Les termes

n! n1 !n2 !...nk !

n n n n! a 1 a 2 ...ak k n1 !n2 !...nk ! 1 2

k

avec

∑ ni = n

sont appelés coefficients multinomiaux.

i =1

I.2.f. Combinaisons (avec répétition) Question: Combien y-a-t-il de façons de placer 4 boules indiscernables dans 3 tiroirs? Réponse: On va réduire ce problème au problème du code binaire présenté au Ch.1.2.d. On désigne les boules par des « 0 » et les tiroirs par des « 1 ». On place le premier « 1 » à la première position. Les zéros entre ce premier « 1 » et le deuxième « 1 » correspondent aux boules dans le premier tiroir, les zéros entre le deuxième « 1 » et le troisième « 1 » correspondent aux boules dans le deuxième tiroir et les zéros situés à droite du troisième « 1 » correspondent aux boules dans le troisième tiroir. Par exemple : 1000101 signifie qu’il y a trois boules dans le premier tiroir, une dans le deuxième tiroir et aucune dans le troisième tiroir. 1110000 signifie que les 4 boules sont dans le troisième tiroir. Puisque on a toujours un chiffre « 1 » à la première position on cherche le nombre des codes binaires de longueur 4+3-1= 6 qui contient 3-1=2 chiffres « 1 ». Donc il y a C26 = 15 façons de placer 4 boules indiscernables dans 3 tiroirs.

Généralisation: k boules distribuées dans n tiroirs : Cnk+ k −1 = Cnn+−k1−1 Question: Combien y-a-t-il de vecteurs (x1, x2, x3) distincts à composantes entières et non négatives satisfaisant x1 + x2 + x3 = 10? Réponse: On va réduire ce problème au problème de tiroirs ci-dessus. Les composantes correspondent aux tiroirs et la somme de composantes correspond au nombre de boules. Donc il y a C212 = 66 tels vecteurs.

Généralisation: vecteurs (x1, x2,…, xn) à composantes entières et non négatives satisfaisant x1 + x2 + … + xn = k : Cnk+ k −1 = Cnn+−k1−1

9

I.3.

Quelques exemples de dénombrement

I.3.a. Bridge Donner le nombre total de mains au bridge. 13 Pour avoir une main, on doit choisir 13 cartes parmi 52 : C52 = 635.013.559.600 possibilités. Combien de mains sans honneurs, c’est-à-dire sans cartes plus grandes que le 10 (10, Valet, Dame, Roi, As), y a-t-il au bridge ? 13 Il faut cette fois choisir les 13 cartes parmi 32 : C32 = 347.373.600 possibilités.

1.3.b. Poker Une main de poker est la donnée de 5 cartes choisies au hasard dans un jeu de 52 cartes. On associe à chaque main une valeur selon les combinaisons particulières qu'elle présente. Les différentes combinaisons valables sont décrites dans le tableau cidessous, avec la valeur qui leur est associée.

Valeur 8

Main quinte flush

7

carré

6

full

5

couleur

4

suite

3

brelan

2

2 paires

1

1 paire

0

rien de tout cela

Détails 5 cartes qui se suivent de la même couleur 4 cartes de même hauteur

Exemple 7♠,8♠,9♠,10♠,V♠ 9♣,9♦,9♥,9♠,As♠

3 cartes de même hauteur et 8♣,8♦,8♥,As♥,As♠ une paire 5 cartes de même couleur et As♣,D♣,9♣,8♣,7♣ qui se ne suivent pas 5 cartes qui se suivent et ne 10♣,9♣,8♣,7♣,6♥ sont pas de même couleur 3 cartes de même hauteur 7♣,9♦,9♥,9♠,As♠ 2 fois 2 cartes de même hauteur 2 cartes de même hauteur

Total

Nombre 36 624 3 744 5 112 9 180 54 912

9♣,9♦,V♥,V♠,As♠

123 552

R♣,R♦,9♥,D♠,V♠

1 098 240

9♣,8♦,5♥,V♠,As♠

1 303 560 2 598 960

10

Dans la suite, on caractérise une carte par sa couleur (Pique, Cœur, Carreau, Trèfle) et sa hauteur (2, 3, 4, ... Valet, Dame, Roi, As).

Le nombre total de mains est le nombre de choix de 5 cartes parmi les 52 du jeu. Il y a donc C525 =2.598.960 mains. V=8 : Pour obtenir une quinte flush, il faut choisir une couleur (4 choix) puis une hauteur, par exemple la plus haute de la suite (9 choix). V8 = 4*9 = 36 quintes flush. V=7 : Pour obtenir un carré, il faut choisir une hauteur (13 choix) puis la dernière carte 1 de la main ( C48 = 48 choix). V7 = 48*13 = 624 carrés.

V=6 : Pour obtenir un full, il faut choisir la hauteur du brelan (13 choix) et ses couleurs ( C43 = 4 choix) puis la hauteur de la paire, qui ne peut pas être la même (12 choix) et ses couleurs ( C42 = 6 choix). V6 = 13*4*12*6=3.744 full. V=5 : Pour obtenir une couleur, il faut choisir la couleur (4 choix) puis les hauteurs 5 ( C13 choix). Mais en procédant ainsi, on compte aussi les quintes flush, qu'il faut donc soustraire. 5 V5 = 4* C13 - V8=5.112 couleurs.

V=4 : Pour obtenir une suite, il faut choisir la hauteur de la carte la plus haute (9 choix) puis la couleur de chaque carte(45 choix). De nouveau, il faut en soustraire le nombre de quintes flush. V4 = 9*45-V8 = 9.180 suites. V=3 : Pour obtenir un brelan, il faut choisir la hauteur du brelan (13 choix) et ses couleurs ( C43 = 4 choix), puis les hauteurs des 2 cartes restantes, forcément différentes 2 pour ne pas avoir un full ( C12 = 66 choix) et leurs couleurs (42 choix). 2 V3 = 13*4* C12 *42=54.912 brelans.

Alternative 1 : On peut aussi choisir la hauteur du brelan (13 choix) et ses couleurs ( C43 = 4 choix), puis 2 cartes parmi les 48 cartes restantes (la 49ème donne un carré) 2 donc C48 choix. Il faut alors en soustraire le nombre de full : 2 V3 = 13*4* C48 -3744= 54 912.

11

Alternative 2 : On peut encore choisir deux cartes parmi les 49 restantes ; dans ce cas, il faut soustraire quatre fois le nombre de carrés : 2 V3 = 13*4* C49 - 3744 - 4*624= 54 912.

2 = 78 V=2 : Pour obtenir deux paires, il faut choisir la hauteur de chaque paire ( C13

choix), la couleur des 4 cartes des paires ( C42 * C42 = 36) puis la hauteur et la couleur de la dernière carte (11*4 = 44 choix). V2 = 6*13*6*6*11*4=123.552 doubles paires. V=1 : Pour obtenir une paire, il faut choisir la hauteur (13 choix) et les couleurs 2 ( C42 choix) de la paire, puis 3 hauteurs différentes ( C12 choix) et les couleurs des 3 3 cartes restantes (4 choix). 2 V1= 13*6* C13 *43 = 1.098.240 paires.

V=0 : Le nombre de mains sans aucune combinaison valable est la différence entre le nombre total de mains et le nombre de celles qui ont une valeur plus grande que 1. V0=2.598.960 - (V8 + V7 + V6 + V5 + V4 + V3 + V2 + V1) = 1.303.560. Alternative1 : Pour n’avoir ni carré, ni full, ni brelan, ni deux ni une paire on a 5 52*48*44*40*36/5! = 45* C13 choix. Il faut ensuite en soustraire le nombre des quintes flushs, des couleurs et des suites. 5 V0= 45* C13 - 36 - 5112 – 9180 = 1.303.560. 5 Alternative2 : Il y a ( C13 - 9) choix de valeurs qui ne forment pas une suite de valeurs consécutives. Pour ne pas avoir des cartes de même couleur on a 45- 4 possibilités. Par conséquent on a : 5 V0=( C13 - 9)*(45-4)= 1.303.560.

12