Approfondissements de lycée/Dénombrement de base

Dénombrement

Le dénombrement est aussi connu sous le nom d'analyse combinatoire; c'est une branche des mathématiques qui vise à compter les éléments dans des ensembles finis. Elle est popularisée au 17^e siècle en Occident par Pascal (1623-1662) et Fermat (1601-1665). Elle avait alors pour objet la résolution des problèmes de dénombrement, provenant de l'étude des jeux de hasard. Elle était déjà utilisée avant dans le monde Arabe et en Chine.

Cette discipline permet d'aborder le genre de problème suivant. Nous savons comment compter de manière séquentielle: 1, 2, 3, 4, 5, 6, 7, 8 ... Mais combien y-a-t-il de solutions différentes à l'équation

x₁ + x₂ + x₃ = 8

où x_n est un nombre entier positif (zéro y compris). La réponse naturelle serait d'écrire chaque solution unique et compter combien il en existe. Cette méthode marchera éventuellement mais elle est lente et fastidieuse. Existe-t'il une meilleure méthode plus efficiente ? La réponse est naturellement oui. Avant d'aller plus avant, revenons aux bases d'abord.

Ces dernières envisagent quelques situations courantes; le but du jeu étant de s'y ramener. Le dénombrement devient une discipline assez abordable du moment qu'on se dote de la bonne grille de lecture. Il suffit en effet de se poser deux questions:

y-a-t-il des répétitions ?
y-a-t-il un ordre ?.

Liste ordonnée avec répétition

Le code confidentiel de carte bleu est un nombre à quatre chiffres. Les chiffres peuvent être répétés. Combien y-a-t-il de codes différents ?

Pour avoir la solution, il suffit d'appliquer le principe multplicatif:

il y a 10 possibilités (0-9) pour le 1^er chiffre;
il y a encore 10 autres possibilités pour le 2^e chiffre;
de même pour l'avant-dernier et le dernier chiffre.

Il y a donc en tout $10\times 10\times 10\times 10=10^{4}$ possibilités.

Du point de vue mathématique, construire une liste ordonnée de p éléments (on parle alors de n-uplet) choisis dans un ensemble de n éléments conduit à $n^{p}$ possibilités.

Sélection ordonnée ou liste ordonnée sans répétition

Supposons qu'il y a 20 chansons dans votre collection de Mp3. Vous demandez à votre micro de sélectionner aléatoirement 10 chansons et de les jouer dans l'ordre où elles sont sélectionnées, combien de manières y-a-t'il de sélectionner les 10 chansons ? Ce type de problèmes est appelé dénombrement de sélection ordonnée, puisque l'ordre dans lequel les choses sont sélectionnées est important. C.a.d. si une sélection est

1, 2, 3, 4, 5, 6, 7, 8, 9 et 10

alors

2, 1, 3, 4, 5, 6, 7, 8, 9 et 10

est considérée comme un sélection différente.

Il y a 20 manières de choisir la première chanson puisqu'il y a 20 chansons, puis il y a 19 manières de choisir la deuxième chanson et 18 manières de choisir la troisième... et ainsi de suite. Par conséquent, le nombre total de manière peut être calculé en considérant le produit suivant :

20\times 19\times 18\times 17\times 16\times 15\times 14\times 13\times 12\times 11\,

ou noté de manière plus compacte :

{\frac {20!}{10!}}

Ici, nous utilisons la fonction factorielle, définie par $0!=1$ et $n!=(n-1)!\times n$ . (En d'autres mots, $n!=1\times 2\times 3\times ...\times n$ )

En général, le nombre de sélections ordonnées et sans répétition de m articles sur n articles est :

{\frac {n!}{(n-m)!}}

L'idée est que nous les annulons tous, sauf les m premiers facteurs du produit n !.

On considère ici une liste ordonnée sans répétition; on préfère parler d'arrangements. Un cas particulier est de sélectionner une liste ordonnée de n éléments parmi n éléments. Il y a n façons de choisir le premier élément, n-1 pour le second, ..., 2 pour l'avant-dernier et puis 1 seul pour le dernier. Cela fait en tout n!, ce qui est confirmer par la formule précédente, où on a pris m=n. On parle alors de permutations.

Sélection non-ordonnée sans répétition

Sur 15 personnes de votre classe de mathématiques, 5 ont été choisies pour représenter la classe dans une compétition de mathématiques. Il ne peut bien-sûr pas y avoir de répétitions. Combien y a-t'il de manières de choisir les cinq étudiants ? Ce problème est appelé un problème de sélection non-ordonnée sans répétition, i.e. l'ordre dans lequel vous sélectionnez les étudiants n'est pas important. C.a.d. si une sélection est

Jean, Luc, Sylvie, Barbara, Jacques

une autre sélection équivalente est

Luc, Jean, Sylvie, Jacques, Barbara.

Il existe

{\frac {15!}{10!}}

manières de choisir les 5 candidats dans une sélection ordonnée, mais il existe 5! permutations des mêmes cinq candidats. (C'est à dire, 5! permutations différentes sont les mêmes combinaisons). Par conséquent, il y a

{\frac {15!}{10!5!}}

manières de choisir 5 étudiants pour représenter votre classe.

En général, pour choisir (sélection non-ordonnée) m candidats à partir de n, il existe

{\frac {n!}{m!(n-m)!}}={n \choose m}

manières. Nous avons donné la formule pour les sélections ordonnées de m candidats à partir de n, puis, nous avons divisé par m! parceque chaque sélection non-ordonnée était comptée comme m! sélections ordonnées.

Exemples

Exemple 1 De combien de manières différentes les lettres du mot BOOK peuvent-elles être arrangées ?

Solution 1 4! manières si les lettres sont toutes distinctes. Puisque O est répétée deux fois, il existe 2! permutations. Par conséquent, il existe 4!/2! = 12 manières.

Exemple 2 Combien existe-t'il de manières de choisir 5 carreaux d'un jeu de 32 cartes ?

Solution 2 Il existe 8 carreaux dans un jeu de 32 cartes. Donc, il existe $8 \choose 5$ manières.

{8 \choose 5}={\frac {8!}{3!5!}}={\frac {8\times 7\times 6}{6}}=56

Tableau récapitulatif

Le tableau suivant fait le point sur les différents cas. On remarquera que nous n'avons pas traité le cas "avec remise et non ordonné".

Tirages	Ordonné	Non ordonné
Sans remise	$A_{n}^{p}$	$C_{n}^{p}$
Avec remise	$B_{n}^{p}$	$\blacksquare$