1 Dénombrement

8/9/2019 1 Dnombrement

1/9

Dnombrement

_____________

I Situation fondamentale

a) Le schma suivant prsente une suite de n cases :

1re

case 2me

case nime

case

Dans la premire case, on veut placer un objet mathmatique a1, dans la deuxime case un

objet a2, dans la nime

case un objet an avec :

p1 possibilits de choix pour a1


pn possibilits de choix pour an

Combien y a-t-il de rsultats possibles ?

Rponse : Il sagit dun cas multiplicatif :

Le nombre de rsultats possibles diffrents estp1p2pn.

b) La suite des n objets a1 a2 an est donne par lcriture (a1, a2, ,an). Daprs le

paragraphe prcdent, on obtient le thorme fondamental suivant :

On considre toutes les suites de n objets (a1, a2, , an) que lon peut former en ayant :



pn possibilits de choix pour an

Alors le produitp1p2pn donne le nombre de ces suites distinctes que lon peut obtenir.

c) Suite et ensemble

La notation { a1, a2, , an } ne dsigne pas une suite de n objets, mais cette notation{ a1, a2, , an } dsigne lensemble dont tous les lments sont a1, a2, , an ; lordre dans

lequel on crit ces lments nintervient pas pour dfinir lensemble.

Ainsi {1, 2, 3}= {3, 2,1} mais (1, 2, 3)(3, 2,1).


2/9

II Application du thorme fondamental

On se donne un ensemble de n lments, avec n entier naturel non nul.

1 Suites dep lments de

Avecp entier naturel :

Pour former une suite (a1, a2,, ap) dep lments de , on a n possibilits de choix pour a1dans , on a n possibilits de choix pour a2 dans ,, on a n possibilits de choix pour apdans . Cela justifie le rsultat suivant :

Le nombre de suites (a1, a2,, ap) dep lments de est donne par le produit n n n o

on a crit n,p fois. Ce nombre est donc gal np

.

Exemple : Le nombre de triplets (suite de 3 lments) de lensemble {1, 2, 3, 4} est 43=64.

2 Arrangements

Soitp un entier vrifiant 1p n :

Pour former une suite (a1, a2,, ap) dep lments de , distincts 2 2,

on a n possibilits de choix pour a1 parmi les n lments de une fois a1 pris dans ,on a n1 possibilits de choix pour a2 parmi les n1 lments

restant de qui sont distincts de a1

une fois les 2 lments distincts a1, a2 pris dans , on a n2 possibilits de choix poura3 parmi les n2 lments restants de qui sont distincts de a1, a2

une fois lesp1 lments distincts 2 2, a1, a2,ap1 pris dans , on a n(p1)

possibilits de choix pour ap parmi les n(p1)=np+1 lments restant de qui sont

distincts de a1, a2, ,ap1

Le nombre de suites dep lments de , distincts 2 2, est donc donn par le produit desp

entiers n(n1)(n2)(n[p1]) = n(n1)(n2)(np+1).

On obtient ainsi la dfinition et le thorme suivant :

Un arrangement dordrep de est par dfinition une suite dep lments de , distincts deux deux.

Le nombre darrangements dordrep, des n lments de est gale au produit desp entiers

compris entre n et np+1 ; on note pnA pour ce nombre.

On a lgalit : pnA = n(n1)(n2)(np+1) .

Exemple Les arrangements dordre 3 de {1 ;2 ;3 ;4} sont au nombre de 34A = 432=24.


3/9

3 Permutations

Toute suite de n lments, constitue par tous les n lments de , est automatiquement unarrangement dordre n de .Rciproquement un arrangement dordre n de est une suite de n lments distincts 2 2 de

: Elle est constitue de tous les n lments de .

Dans le cas particulier du paragraphe prcdent op=n, on obtient la dfinition et lethorme suivant :

Les permutations de sont toutes les suites de n lments, constitues par tous les lmentsde ; les permutations de sont aussi tous les arrangements dordre n de .

Le nombre de permutations de est not n! : n!= nnA = n(n1)(n2)21.

n! est le produit des n entiers compris entre 1 et n.

Exemple Le nombre de permutation de lensemble {1 ; 2 ; 3 ; 4 }est 4 ! = 4321=24.

4 galits classiques

a) Par convention de notation : 0 ! =1 et sans problme (n+1) ! = n !(n+1) pour tout entiernaturel n.

b) p et n tant des entiers vrifiant 1 pn ,

Lorsquep n : n ! = n(n1)(n2)(np+1)(np)(np1)(2)(1) ce qui donne :

n ! =

p

nA (np) ! Lorsquep=n : n ! = nnA =

n

nA 0 ! do n ! =p

nA (np) !

Finalement avecp et n entiers naturels vrifiant 1 pn, on a :)!(

!

pn

nA

p

n

= .


4/9

4 Exemples de dnombrements

1) On a 10 livres. valuer le nombre de faons de ranger 4 de ces 10 livres sur une tagre.________________________________________

Rsolution : Ranger 4 des 10 livres sur ltagre revient se donner (l 1, l2, l3, l4) un

arrangement dordre 4 dans lensemble des 10 livres [pour placer ces quatre livres surltagre dans lordre suivant : On pose en premier l1, en second l2, en troisime l3, enquatrime l4].Le nombre cherch est donc : 410A =10987=5040 .

2) a) valuer le nombre de tiercs dans lordre dans une course de 15 chevaux.b) Si lon considre que seuls 5 chevaux peuvent tre placs, valuer le nombre de tiercs

que lon peut retenir.__________________________________________

Rsolution : a) On considre quun tierc est un arrangement dordre 3 parmi les 15 chevaux :

Le nombre de tiercs est donc :3

15A

=151413= 2 730 .b) On considre quun tierc que lon peut retenir est un arrangement dordre 3 parmi les 5chevaux pouvant tre placs: Le nombre de ces tiercs est donc : 35A =543= 60 .

On remarque que la proportion de tiercs que lon peut retenir273

6315

35 =

A

A0,022 est trs

petite pas rapport la proportion de chevaux retenus3

1

15

5= 0,33.

3) valuer le nombre de faons de rpartir 6 postes de travail entre 6 ouvriers._________________________________

Rsolutions : On numrote les postes de travail de 1 6, rpartir les 6 postes de travail entreles 6 ouvriers revient se donner une permutation des 6 ouvriers (o1, o2, o3, o4, o5, o6) pourindiquer que louvrier oisoccupe du poste de travail ni pour 1i6.Le nombre cherch est le nombre de permutations des 6 ouvriers, il est gal :6 ! = 654321= 720 .


5/9

III Combinaisons

1. Dfinition

On se donne un ensemble de n lments ( avec n dans ).

Avecp dans , une combinaison dordrep de est une partie de p lments.

Remarques :

, lensemble vide, est la seule combinaison dordre 0 de .

Avecp dans tel que 1pn :

Toute combinaison dordrep de scrit {1, 2, , p}o 1, 2, , p sontp lments

distincts de , l'ordre dans lequel sont donns sont ces lments nintervient pas pour dfinir

cette combinaison.

Cette combinaison dordrep de s'obtient en crivant (1, 2, , p), une des pnA suites de

p lments distincts 2 2 de , on remplace ensuite les parenthses par des accolades.

Il ne peut donc y avoir plus de pnA combinaisons dordrep de .

Cas op=n : est la seule combinaison dordre n de .

Cas op=1 : Soit ={1, 2, , p} alors {1}, {2}, {n}sont toutes les combinaisons

dordre 1 de .

Il y a exactement n combinaisons dordre 1 de .

Si n


6/9

On a alors lgalit pnA =Np! soit :N=

!p

Ap

n est le nombre de combinaisons dordrep des n

lments de .

3. Notation

p

nC

Avecp et n entiers naturels, la notationp

nC ou

p

ndsignent le nombre de combinaisons

dordrep dans un ensemble n lments.

Daprs les paragraphes prcdents : 1= nnn CC =0

et n=1

nC .

Si n


7/9

Triangle de Pascal

Le tableau suivant donne le coefficient knC la ligne numro n et la colonne numrop.

p 0 1 2 3 4 5 6 7 8 9 10 11 12

n

0 1 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0 0 0

2 1 2 1 0 0 0 0 0 0 0 0 0 0

3 1 3 3 1 0 0 0 0 0 0 0 0 0

4 1 4 6 4 1 0 0 0 0 0 0 0 0

5 1 5 10 10 5 1 0 0 0 0 0 0 0

6 1 6 15 20 15 6 1 0 0 0 0 0 0

7 1 7 21 35 35 21 7 1 0 0 0 0 0

8 1 8 28 56 70 56 28 8 1 0 0 0 0

9 1 9 36 84 126 126 84 36 9 1 0 0 0

10 1 10 45 120 210 252 210 120 45 10 1 0 0

11 1 11 55 165 330 462 462 330 165 55 11 1 0

12 1 12 66 220 495 792 924 792 495 220 66 12 1

13 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13

14 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91

15 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 1

16 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 5

17 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 23

On y lit par exemple que :

4

13C =715 .

Sachant que la formule du binme scrit : (x+y)n= nn

nn

n

iini

n

n

n

n

nyCyxCyxCyxCxC ++++++

1111110 ......

daprs le tableau, par exemple : (x+y)6=x

6+ 6x

5y + 15x

4y

2+ 20x

3y

3+ 15x

2y

4+ 6xy

5+y

6.


8/9

IV Problmes

Dans un ensemble de 20 appareils, 5 sont dfectueux. On ralise un tirage en y prlevant

au hasard, simultanment 3 appareils.

1. Combien peut on raliser de tirages diffrents de 3 appareils?2. Combien de tirages ne comporteront aucun appareil dfectueux ?3. Combien de tirages comporteront au moins un appareil dfectueux ?4. Combien de tirages comporteront exactement un appareil dfectueux ?5. Combien de tirages comporteront au moins deux appareils dfectueux ?

______________________________________________

1. Les tirages sont les combinaisons dordre 3 de lensemble de 20 appareils ; le nombre

des tirages est donc =

=

23

181920320C 20193=1140.

2. Les tirages ne comportant aucun appareil dfectueux sont les combinaisons dordre 3

parmi les 15 appareils non dfectueux ; le nombre de ces tirages est donc

=

= 23

131415315C 5713=455.

3. Soit T lensemble des3

20C =1140 tirages et T0 lensemble des3

15C =455 tirages ne

comportant aucun appareil dfectueux.

Lensemble U des tirages comportant au moins un appareil dfectueux est donn par U=T\T0 :

U est lensemble obtenu lorsquon retire de lensemble des 1140 tirages de T les 455 tirages

de T0. Le nombre des lments de U est ainsi 1140455=685.

T=U T0

T

T0

UT0=

4. Se donner un tirage t comportant exactement un appareil dfectueux revient remplir la

suite de 2 cases de la manire suivante

- dans la premire case on place a un des 5 appareils dfectueux,

- dans la deuxime case on place {b, c} une des2

15C combinaisons dordre 2 parmi les 15

appareils non dfectueux.

Le tirage test alors donn par lcriture t={a, b, c}.___________________________

Le nombre de tirages tcomportant exactement un appareil dfectueux est donn par la

multiplication 52

15C o 52

15C =52

1415=5715=525.

525 est le nombre dlments de T1, lensemble des tirages comportant exactement 1 appareil

dfectueux.

5. U lensemble des tirages comportant au moins un appareil dfectueux contient T1,

lensemble des tirages comportant exactement 1 appareil dfectueux. On retire des 685lments de U les 525 lments de T1 pour obtenir U\T1 (lensemble des lments de U ne se

trouvant pas dans T1) qui est alors lensemble des tirages comportant au moins 2 appareilsdfectueux. Le nombre de ces tirages est donc : 685525= 160 .


9/9

Exemple du loto

Au loto, on remplit un bulletin en notant 7 numros (nombres entiers distincts) compris entre

1 et 49, lordre dans lequel on choisit ces numros nintervient pas.

Ce nest quensuite que lon prend connaissance d une liste-type L qui comporte 6 numros

distincts compris entre 1 et 49 ; on est gagnant si au moins 3 numros du bulletin figurent

dans L.1. Dterminer le nombre de bulletins possibles.2. Dterminer le nombre de bulletins comportant les six numros de la liste-type L.3. Dterminer le nombre de bulletins possibles comportant exactement 3 numros de L.4. Dterminer le nombre de bulletins possibles comportant exactement 4 numros de L.5. Dterminer le nombre de bulletins possibles comportant exactement 5 numros de L.

______________

L est une combinaison donne dordre 6 parmi les 49 premiers entiers naturels non nuls, L est

inconnue lorsquon remplit le bulletin.

1. Un bulletin est un ensemble de 7 lments parmi les 49 premiers entiers naturels non nuls :

Cest une combinaison dordre 7 parmi les 49 premiers entiers naturels non nuls.

Le nombre de bulletins possibles est donc7

49C = 85 900 584 .

2. Se donner un bulletin comportant les 6 numros de la liste L ne revient plus qu se donner

un numro parmi les 43 autres numros possibles.

Le nombre de bulletins comportant les six numros de la liste L est donc 43.

3. Se donner un bulletin B ayant exactement 3 numros de la liste L revient remplir la suite

de 2 cases de la manire suivante :- dans la 1

recase on place {, , } une des 36C combinaisons dordre 3 des 6 lments de L

- dans la 2me

case on place { a, b, c, d} une des 443C combinaisons dordre 4 parmi les 43

nombres de {1, 2, 3, , 48, 49}\L.

Il sagit dcrire B= {, , , a, b, c, d}._______________________________________

Le nombre de bulletins ayant exactement 3 numros de la liste L est ainsi donn par :3

6C 4

43C = 2 468 200 .

4. Comme la question 3, on montre que :


6C 3

43C = 18 5115 ..

5. Comme la question 3, on montre que :


6C 2

43C = 5 418 .

Documents

1 Dénombrement