Le dénombrement

Analyse combinatoire

Mathématiquement, on dénombre un ensemble pour connaître son cardinal. Ce peut être un simple comptage ou utiliser des techniques moins... primaires. Autrefois, ces techniques étaient étudiées au lycée afin d'introduire le vaste chapitre des probabilités. Aujourd'hui, ces dernières sont enseignées de plus en plus tôt dans les études tandis que l'analyse combinatoire connaît un sort inverse. Pourtant, d'un point de vue théorique, il est plus normal que l'apprentissage du dénombrement précède celui des probabilités puisqu'il permet de déterminer l'univers des possibilités.

On dispose d’un certain nombre d’éléments et on cherche à les « combiner ». Combien existe-t-il de possibilités ? Il existe quatre types de situations.

La permutation

La première de ces situations est celle où l’on dispose de la TOTALITÉ de n éléments dans un certain ORDRE. Ces éléments peuvent être réagencés si l'on permute l'ordre dans lequel ils apparaissent. Combien de possibilités ? Réponse : n! qui se prononce factorielle (de) n ou n factorielle. Par convention, 0! = 1. Exemple de factorielle :

Nombre de mots de cinq lettres pouvant être écrits avec A, B, C, D et E : 5 × 4 × 3 × 2 × 1 = 5! = 120. Dans cet exemple, on obtient le mot ABCDE mais si l'on permute les deux premières lettres on obtient BACDE et ainsi de suite.

Note : la factorielle est une notion importante en statistiques. On la retrouve dans la formule de la loi de Poisson. Les mathématiques financières utilisent également les factorielles.

Pour information, il existe des notions issues de la factorielle qui ne sont pas utilisées en statistiques (primorielle, multifactorielle, superfactorielle, hyperfactorielle et sous-factorielle). L’article « Factorielle » de Wikipédia épanchera votre soif de culture générale sur le sujet, mais pas forcément sur son utilité pratique.

La p-liste (ou arrangement avec répétition)

Là aussi, l’ordre a son importance, mais on peut réutiliser un élément plusieurs fois (p fois). Le nombre de possibilités est chaque fois égal à n. Peu importe que ce n soit inférieur, égal ou supérieur à p. On cherche donc np. Sans toujours l'appeler p-liste, c'est en principe par ce calcul que sont abordées au lycée les probabilités d'évènements indépendants.

Exemple de p-liste : nombre de possibilités de codes de carte bancaire à quatre chiffres. Réponse : 104 = 10 000.

L’arrangement (sans répétition)

Cette notion est un peu moins utilisée. On ne prend qu’une seule fois un certain nombre d’éléments de l’ensemble (contrairement à la permutation) en s’attachant à l’ordre.

arrangement

Exemple d’arrangement : quinze chevaux sont partants. Combien de possibilités de tiercés dans l’ordre existe-t-il ?

arrangement (exemple)

S’il n’y avait que trois chevaux partants, on se trouverait dans la situation d’une factorielle. Et comme l’arrivée des deux premiers impliquerait forcément la place du troisième, on peut constater la double égalité suivante :

double égalité

Une façon très matheuse de présenter les choses est de considérer d'une part l'ensemble des places d'arrivée (premier, deuxième...) et d'autre part l'ensemble des partants, puis de considérer l'arrangement comme une injection du premier ensemble sur le deuxième (du moins en l'absence d'ex aequo) au contraire de la permutation qui est une bijection.

La combinaison

À la différence de l’arrangement, on se moque de l’ordre. La notion de combinaison est particulièrement importante en statistiques. Passons tout de suite à la formule (et aux deux formes d’écriture en usage, le C étant de moins en moins employé). Avec Excel, utilisez la fonction COMBIN.

combinaison

n et p sont parfois nommés les coefficients binomiaux (on les retrouve dans la formule de la loi binomiale). Plus souvent, c'est la combinaison elle-même qui est qualifiée de coefficient binomial. Elle DÉNOMBRE les branches de l'arbre de probabilités qui satisfont à la condition cherchée.

On en déduit quelques combinaisons simples :

combinaisons = 1

combinaisons = n

Exemple : combien de mains de cinq cartes sont-elles possibles sur un jeu de 52 ? Réponse : 2 598 960.

Et combien avec deux as seulement ?

exemple

Autre exemple : pendant les trois minutes qui précèdent une réunion, les trente participants se serrent tous la main. 435 poignées de mains échangées ! Effarant...

Pour une utilisation avec une calculatrice TI, rendez-vous en page loi binomiale à la calculatrice.

Le triangle de Pascal est une « table » des combinaisons, réalisable sur tableur en quelques secondes. Le binôme de Newton en constitue une utilisation célèbre.

Pascal

On indique 1 pour chaque cellule de la colonne 0, également 1 sur la diagonale n × p et tous les autres nombres sont la somme de celui du dessus et de celui dessus à gauche. Extrait :

triangle de Pascal

On lit notamment qu'il y a 55 combinaisons possibles de deux évènements pris parmi onze.

Ce triangle se résume d’ailleurs de façon très simple par une relation de récurrence :

récurrence

Autre particularité de ce triangle, la proportion qui existe entre deux nombres consécutifs sur la même ligne est la même qui existe entre le nombre de valeurs à la gauche du premier (inclus) et le nombre de valeurs à la droite du deuxième (inclus). Par exemple 45 / 120 (ligne 10) est égal à 3 / 8 (45 est le troisième nombre en partant de la gauche et 120 est le huitième nombre en partant de la droite).

 

factorielle