Dénombrement

Cours maths Terminale S

Dénombrement :
Ce module est consacré à la définition et au dénombrement des objets pouvant être le résultat d’une expérience aléatoire.
► Sommaire cours maths Terminale S

      A voir aussi :


► Sommaire par thèmes
► Sommaire par notions
► menu 600 VIDEOS       
 

1/ Définition des objets : introduction

Dénombrer, c’est compter des objets.

Ces objets sont créés à partir d’un ensemble E, formé d’éléments.

A partir des éléments de cet ensemble, les objets que l’on peut former sont soit des listes
d’éléments de E soit des sous-ensembles de E.

A la différence des sous-ensembles,

les listes peuvent utiliser plusieurs fois un même élément, et surtout, possèdent un ordre.
Dans les exercices, les objets obtenus sont le résultat d’une expérience aléatoire,
c’est à dire que le hasard intervient dans leur formation.

Le dénombrement de ces objets, lui, n’a rien d’aléatoire,

il est un décompte organisé de tous les résultats possibles d’une telle expérience.


Nous allons maintenant définir avec plus de précisions

les différents objets que l’on peut rencontrer et pour ce, nous allons prendre comme exemple
l’ensemble suivant :

Soit E un ensemble à 4 éléments : E = { a ; b ; c ; d }

Remarques :
1) le nombre d’éléments de E est appelé cardinal de E et noté card E = 4

2) les éléments de E sont 2 à 2 distincts, sinon card E ≠ 4.

Créons, maintenant les conditions d’une expérience aléatoire :
* prenons 4 jetons indiscernables au toucher
* inscrivons sur le premier : a, sur le deuxième : b, sur le troisième : c, sur le dernier : d et plaçons-les dans un sac

1/ Définition des objets : p-uplets
Expérience n°1 :
Tirages successifs avec remise.
* On pioche un premier  jeton, par exemple : b et on le remet dans le sac.
* On pioche un deuxième jeton, par exemple : a et on le remet dans le sac.
* On pioche un troisième jeton, par exemple : a et on le remet dans le sac.
L’expérience est terminée.

Le résultat est noté à l’aide de parenthèses ( b ; a ; a )

Les résultats possibles de cette expérience sont des listes de 3 éléments de E,
avec répétition d’éléments possible.

- Une liste de 3 éléments est appelée un triplet.

- Plus généralement, une liste de p éléments est appelée un p-uplet ou une p-liste.
Attention !
Une liste respecte un ordre : 
( b ; a ; a ) ( a ; a ; b )
Dans une liste, il y a un premier élément, un deuxième élément, etc…

1/ Définition des objets : arrangements
Expérience n°2 :
Tirages successifs sans remise.
* On pioche un premier  jeton, par exemple : b que l’on ne remet pas dans le sac.
* On pioche un deuxième jeton, par exemple : a que l’on ne remet pas dans le sac.
* On pioche un troisième jeton, par exemple : c que l’on ne remet pas dans le sac.
L’expérience est terminée.

Le résultat est noté à l’aide de parenthèses ( b ; a ; c )
Les résultats possibles de cette expérience sont des listes de 3 éléments de E,
sans répétition d’éléments possible.
- Une liste de 3 éléments sans répétition possible est appelée un arrangement de 3 éléments.
- Plus généralement, une liste de p éléments sans répétition possible est appelée un arrangement de p éléments de E.
Remarques :
1) Cette dénomination a pour avantage de bien marquer l’importance de l’ordre dans une telle liste.

2) Un arrangement de p éléments de E est un cas particulier de p-uplet d’éléments de E.

1/ Définition des objets : permutations
Expérience n°2 :
Tirages successifs sans remise.

Cas particulier d’arrangement :
Si l’on réalise autant de pioches sans remise qu’il y a de jetons dans le sac, on obtient alors une liste de tous les éléments de E rangés dans un certain ordre.

Une telle liste est appelée une permutation des éléments de E.


Par exemple : 
( d ; b ; c ; a )  est une permutation des éléments de E.
Et :    ( c ; a ; d ; b )  en est une autre.
Plus généralement : un arrangement de n éléments d’un ensemble E à n éléments est appelé une permutation des éléments de E.

1/ Définition des objets : combinaisons
Expérience n°3 :
Tirages simultanés.
* On pioche trois jetons en une seule fois, par exemple : a, d et c.
Le résultat est noté à l’aide d’accolades : { a ; d ; c }
Les résultats possibles de cette expérience sont des sous-ensembles de E ou parties de E, possédant 3 éléments.

Un sous-ensemble de E comportant 3 éléments est appelé une combinaison de 3 éléments de E.


Plus généralement, une partie de E possédant p éléments
est appelée une combinaison de p éléments de E.

- L’ensemble  { d ; a ; c } possède les mêmes éléments que l’ensemble   { a ; d ; c }
Ils sont donc égaux.
Par conséquent, contrairement aux listes, l’ordre d’écriture des éléments d’une combinaison n’a pas d’importance.

Cette absence d’importance de l’ordre est marquée par l’utilisation de l’écriture avec accolades,
écriture réservée aux ensembles.

2/ Dénombrement : arrangements


Nous savons ce qu’est, par exemple, un arrangement de 3 éléments de E,

mais le problème est maintenant de trouver combien on peut former de listes de ce type.

Deux grandes techniques de dénombrement existent.

Voici la première de ces techniques,
appliquée au dénombrement des arrangements de 3 éléments
de l’ensemble E, défini plus haut :

Technique de l’arbre :
Il y a 4 choix pour le premier élément de la liste.dénombrement : Technique de l’arbre

Puis, à chaque choix fait pour le premier élément
correspond pour le deuxième élément
un même nombre de choix : 3.

( = nombre de choix possibles parmi les (4-1) éléments
  restants, car la liste est sans répétition )

Puis, à chaque choix fait pour le deuxième élément
correspond pour le troisième élément
un même nombre de choix : 2.

( = nombre de choix possibles parmi les (4-2) éléments
  restants, car la liste est sans répétition )

En bout de branches,
nous récupérons les différents arrangements possibles.

A chaque stade de choix, chaque branche « éclatant »
en un même nombre de choix, les arrangements possibles
sont au nombre de : 4x3x2 = 24.

Soit : (4-0)x(4-1)x(4-2).

Ou encore : 4x(4-1)(4-(3-1)).


Technique des cases :
« Fabriquer » un arrangement de 3 éléments de E,
équivaut à remplir les 3 cases suivantes avec des éléments 2 à 2 distincts :

Dénombrement : Technique des cases

Il y a 4 choix possibles pour le premier élément.


Puis le choix du premier élément étant fait, il reste 3 choix possibles pour le deuxième.


Et enfin, le choix des deux premiers éléments étant fait,

il reste 2 choix possibles pour le dernier.

Dénombrement : Technique des cases

Remarque :
cette technique équivalente à celle de l’arbre, est parfois plus pratique quand par exemple un élément de la liste est connu ainsi que sa position.

Cas général : soit un entier naturel  n > 1, et soit p entier naturel tel que : 1 < p < n

Le nombre d’arrangements de p éléments d’un ensemble E à n éléments est noté :  Apn

Et en généralisant le raisonnement tenu sur le cas particulier, on a :


Dénombrement : Technique des cases

2/ Dénombrement : permutations

* Si p = n, on dénombre alors les permutations d’éléments de E.
Sur notre cas particulier, en utilisant par exemple la technique des cases, on trouve qu’il existe : 4x3x2x1 permutations des éléments de E.
Soit : 24 permutations des 4 éléments de E.
Plus généralement, une permutation étant un arrangement de n éléments de E, il en existe : 
Soit :
Cas général : pour tout entier  n > 1
Le nombre de permutations d’un ensemble à n éléments est noté : n! (se lit "factoriel n")
Avec :
Remarques :
1) D’un point de vue calculatoire ( qui perd le sens du dénombrement ) :    Il s’agit tout simplement du produit des n premiers entiers.

2) Par convention :  0! = 1

2/ Dénombrement : p-uplets

Toujours avec notre exemple, en dénombrant à l’aide de la technique des cases
et en tenant compte du fait que la répétition d’un même élément est possible :

on trouve qu’il existe : 4x4x4 triplets possibles, soit 64 triplets formés avec les éléments de E.

Cas général
: soit un entier naturel
n > 1, et soit p entier naturel tel que :  p > 1
Le nombre de p-uplets d’un ensemble à n éléments est :  np
Remarque :
Comme il peut y avoir répétition des éléments de E, p peut être strictement plus grand que n.

2/ Dénombrement : combinaisons
Considérons la combinaison de 3 éléments de E : { a ; b ; c }
En permutant ses éléments, il est possible de former des arrangements de 3 éléments de E.

Et le nombre de permutations d’un ensemble de 3 éléments étant : 3!, il est donc possible à partir de cette combinaison de former 6 arrangements de 3 éléments de E.
On peut évidemment faire de même avec les autres combinaisons de 3 éléments de E, obtenant ainsi tous les arrangements de 3 éléments de E.

De plus, deux combinaisons différentes ne peuvent générer deux arrangements identiques.

Donc, si nous notons le nombre de combinaisons de 3 éléments de E, par analogie avec la notation    des arrangements de 3 éléments de E, on a alors :


En effet, les combinaisons possibles sont :
Généralisons ce raisonnement au cas d’une combinaison de p éléments
d’un ensemble E à n éléments.

Chaque combinaison de p éléments, par permutations, génère p! arrangements

de p éléments de E.
Donc, avec les notations utilisées précédemment : 
Or, 
Donc : 
Ce nombre est plus souvent noté :    même si cette écriture est moins parlante.
En multipliant numérateur et dénominateur par :  (n - p)! , on obtient également :


Cas général : soit un entier naturel
n > 1 , et soit p entier naturel tel que :  0 < p < n

Dénombrement : combinaisons

avec pour p ≠ 0
Remarques sur cette formule :

1° Cas particuliers
Cas p = 0 :
Nous avons démontré cette égalité pour  p > 1 mais non pour p = 0 car alors
la notion de liste n’a plus de sens.

Par contre, un sous-ensemble de E possédant 0 éléments existe, il est unique et il s’agit de l’ensemble vide.
On a donc :
Pour p = 0 :  n’a aucun sens, par contre :

Et donc, la deuxième moitié de la formule reste vraie pour p = 0


Cas p = 1 :
Il existe autant de sous-ensembles de E à 1 élément que d’éléments de E donc :
On peut retrouver ce résultat par le calcul :

Cas p = n :

Il n’existe qu’un sous-ensemble de E à n éléments c’est E donc : 
On peut retrouver ce résultat par le calcul : 

2°  Utilisation pratique de cette formule
Pour savoir calculer avec cette formule, le mieux est de toujours garder en tête comment elle a été démontrée.

On utilisera donc pour un calcul direct de « p parmi n », le résultat du milieu.

Exemple : calculons le nombre de combinaisons de 3 éléments d’un ensemble de cardinal 8.
nb de listes de 3 éléments, sans répétitions.
D’un point de vue purement pratique :

On part de 8 et on enlève 1,

jusqu’à obtention de 3 facteurs,
représentant les 3 choix successifs.
factorielle 3, nb de permutations de 3 éléments.

= 8 x 7 = 56
Bien entendu, le calcul que l’on vient de faire peut vite devenir compliqué pour des grands nombres et on utilisera alors la calculatrice.

Mais il est à privilégier chaque fois que cela est possible.

La deuxième partie de la formule sert surtout dans le cas de démonstrations de formules et d’égalités concernant « p parmi n ».

3/ Combinaisons : formules
Formule n° 1 :
pour tous n et p entiers naturels tels que 0 < p < n  :
Conséquence :
* Démonstration par le calcul

* Démonstration en raisonnant sur les ensembles :

est le nombre de sous-ensembles de E contenant p éléments.

Or, choisir p éléments pour former un ensemble, c’est écarter les (n-p) éléments restants de E.


A chaque sous-ensemble de p éléments de E correspond donc un sous-ensemble de (n-p) éléments de E.


Il y a donc autant de sous-ensembles de p éléments que de sous-ensembles de (n-p) éléments.


Par conséquent : « p parmi n » = « (n-p) parmi n »


Formule n° 2 :
pour tous n et p entiers naturels tels que   n < p < n - 1
La démonstration par le calcul fera l’objet d’un R.O.C dans la partie exercices de votre espace membre.

* Démonstration en raisonnant sur les ensembles :
1 <  n - 1  donc, considérons un ensemble E constitué d’au moins deux éléments.

Appelons a, un élément quelconque de E.


Soit une combinaison de p éléments de E contient a, soit elle ne le contient pas.


Notons k le nombre de combinaisons à p éléments, contenant a et notons k’
le nombre de combinaisons à p éléments ne contenant pas a.

k + k' =
Or, pour former une combinaison de p éléments de E contenant a, il faut choisir a puis choisir les (p-1) éléments restants parmi les (n-1) éléments de E différents de a.
k est donc égal au nombre de combinaisons de (p-1) éléments d’un ensemble à (n-1) éléments.
D’où :
Pour former une combinaison de p éléments de E ne contenant pas a, il faut choisir les p éléments parmi les (n-1) éléments de E différents de a.
k’ est donc égal au nombre de combinaisons de p éléments d’un ensemble à (n-1) éléments.
D’où :
Or : 
Donc : 
3/ Combinaisons : triangle de Pascal
Cette formule :  sert entre autres à calculer les  grâce à une astucieuse disposition en tableau :
La formule n’est valable qu’à partir de n = 2  
    triangle de Pascal
  
donc les 2 premières lignes sont à remplir directement.
triangle de Pascaltriangle de Pascal

triangle de Pascal
 
Et sur le même principe, on obtient les lignes suivantes.

triangle de Pascal triangle de Pascal triangle de Pascal

triangle de Pascal
  
  
Au delà, du calcul isolé d’un  
cette technique permet de calculer
tous les
pour un n donné,


  
ce qui peut être utile pour la formule qui suit :
  
  
3/ Combinaisons : formule du binôme de Newton

Formule n° 3 : formule du binôme de Newton.
formule du binôme de Newton

ce qui peut également être noté :

formule du binôme de Newton
La présence de « k parmi n » dans la formule s’explique de la sorte :
par exemple : an-1b1  a pour représentants dans le développement de (a + b)n :
ba...a        aba...a        aaba...a       etc...

Il possède donc autant de représentants que de façons de placer b sur n cases,
les autres étant remplies par des a.

Plus généralement : an-kbk possède autant de représentants que de façons de placer k lettres b sur n cases.
C’est à dire :
Remarques :
1) Cette formule est également valable, de façon plus générale, pour a et b nombres complexes.

2) La somme des exposants de chaque monôme vaut toujours n.

3) En raison de leur rôle dans cette formule, les 
sont aussi appelés coefficients binomiaux.

4) Cette formule se démontre rigoureusement à l’aide d’un raisonnement par récurrence.

Exemple d’utilisation :
Développer  (1 + x)5 à l’aide de la formule du binôme.
Trois des coefficients
sont évidents, d’après la définition des combinaisons :
Un coefficient est à calculer :
Et les deux derniers se déduisent des précédents :

D'où :
Formule que l’on peut « vérifier » par exemple pour x = 2 :

Remarque :
Les coefficients binomiaux pouvait également être trouvés en remplissant le triangle de Pascal jusqu’à la ligne 5, comme vu précédemment.


         Cours complémentaires :

► Evénements

► Probabilités conditionnelles
► Loi binomiale
► Lois continues
► Sommaire cours maths Terminale S

           A voir aussi :

► Sommaire par thèmes
► Sommaire par notions