Dénombrement : Cours-Résumés-Exercices corrigés

Le dénombrement s’emploie à étudier et à dénombrer divers types de groupements que l’on peut faire à partir d’ensembles finis.

Il est né de l’étude des jeux de hasard et s’est fortement développé sous l’influence du calcul des probabilités. Il est par ailleurs lié à la théorie des nombres et à la théorie des graphes.

I- Principes fondamentaux du dénombrement

a- Principe des tiroirs

« Si vous disposez d’une commode avec 5 tiroirs et que vous devez ranger 6 pantalons, alors au moins un des tiroirs contiendra au moins 2 pantalons. »

Plus généralement, si vous avez n « tiroirs » à disposition pour y ranger n+k « objets », alors certains « tiroirs » contiendront plus d’un « objet ».

Exemple :

Dans un village de 400 habitants, peut-on trouver deux personnes qui sont nées le même jour (pas forcément de la même année) ?

Ici, les tiroirs représentent les jours de l’année et les objets les habitants. Seuls 366 habitants peuvent avoir des dates de naissance différentes.

b- Principe de décomposition

Si une opération globale peut se décomposer en k opérations élémentaires successives, ces dernières pouvant s’effectuer respectivement de n1, n2, …, nk manières, alors l’opération globale peut se faire de n1·n2·…·nk manières différentes.

Exemple :

Les localités X et Y sont reliées par trois routes (a, b et c) et les localités Y et Z par deux routes (d et e). Combien y a-t-il de trajets de X à Z en passant par Y ?

Principes fondamentaux du dénombrement - Principe de décomposition

Il y a 6 (= 3·2) trajets possibles : (a, d), (a, e), (b, d), (b, e), (c, d), (c, e).

II- 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, technique de l’arbre et technique des cases

a- Technique de l’arbre :

Dénombrement : arrangements - Technique de l’arbre

Il y a 4 choix pour le premier élément de la liste.

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)).

b- 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 : arrangements - 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.

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é : ${ A }_{ n }^{ p }$

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

III- 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 !

Avec :

IV- 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 ${ C }_{ 4 }^{ 3 }$ le nombre de combinaisons de 3 éléments de E, par analogie avec la notation ${ A }_{ 4 }^{ 3 }$ 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 :