10

A la question « Combien de mots de trois lettres peut-on former avec les lettres A et B ? », il est possible de répondre avec l’élaboration d’un arbre, dont le nombre de branches est constant pour chaque nœud à chacun des niveaux.

En suivant chacun des chemins, il est possible de dénombrer tous les mots ainsi constitués. Si, pour chacun des niveaux, on comptabilise le nombre de branches apparaissant sur chaque nœud de chacun des niveaux de l’arbre, il y a moyen de connaître le nombre total de mots sans les compter.

Le nombre total de mots s’obtient en multipliant les nombres de branches : [latex]2 \times 2 \times 2 = 8[/latex]

De manière plus générale, quel que soit le nombre de niveaux de nœuds et le nombre de branches sur les nœuds de chacun des niveaux, la formule est la suivante : [latex]b_{1} \times b_{2} \times \ldots \times b_{p}[/latex]

De façon plus mathématique, ceci revient à chercher le cardinal^[1] de [latex]X^{p}[/latex] avec [latex]X[/latex] un ensemble constitué de n éléments et [latex]X^{p}[/latex] l’ensemble des p-listes réalisées.

[latex]X = \left\{x_{1}, x_{2}, \ldots, x_{n}\right\}[/latex]

[latex]Card(X) = n[/latex]

[latex]X^{p} = \left\{(a_{1}, a_{2}, \ldots, a_{p}) \mid a_{i} \in X\right\}[/latex]

[latex]Card(X^{p}) = n^{p} = Card(X)^{p}[/latex]

Pour reprendre la question précédente, les mots de 3 lettres sont des 3-listes constitués avec [latex]X = \left\{A, B\right\}[/latex]

[latex]Card(X) = 2[/latex]

[latex]Card(X^{p}) = n^{p} = 2^{3} = 8[/latex]

Nous avons donc bien 8 possibilités pour constituer des mots de 3 lettres avec les lettres A et B.

Il existe une autre question très classique en dénombrement : « Sur une course de 18 chevaux, combien de tiercés sont possibles, c’est à dire combien de podiums peut on anticiper ? ». Pour la première place, il existe 18 possibilités, mais pour la deuxième place il n’en existe plus que 17 puisque qu’un cheval ne peut être qu’à une seule place, et pour la troisième place il ne reste plus que 16 possibilités. Le nombre de podiums possibles est donc de : [latex]18 \times 17 \times 16 = 4.896[/latex]

Ce genre de question nous amène à aller un peu plus loin dans le domaine du dénombrement.