P-liste

Imaginez un code de trois chiffres, chaque chiffre étant choisi parmi 0, 1 et 2. Le code 012 n'est pas le même que 210, car la position de chaque chiffre compte. Le code 001 est aussi admis : un même chiffre peut revenir plusieurs fois.

Chaque code est donc une 3-liste. Il existe trois choix pour la première place, puis trois pour la deuxième et trois pour la troisième, soit 27 codes.

Soit un ensemble fini E contenant n éléments et soit p un entier naturel. Une p-liste d'éléments de E est une suite ordonnée de longueur p. Elle peut se noter (x₁, x₂, …, x_p), où chaque terme appartient à E. Deux p-listes sont égales seulement si elles ont le même élément à chaque position. Une p-liste est ainsi un élément du produit cartésien E^p. Avec répétition autorisée, chacune des p positions offre n choix indépendants, soit $n^{p}n^p$ p-listes.

Sans répétition, un élément déjà choisi ne peut plus réapparaître. Lorsque p est inférieur ou égal à n, le nombre de p-listes sans répétition est :

Cette variante est aussi appelée arrangement de p éléments parmi n. Si p = n, elle devient une permutation des n éléments. Si p est supérieur à n, aucune p-liste sans répétition n'existe.

On forme des codes de longueur 3 avec l'ensemble E = {0, 1, 2}. Les données sont donc n = 3 symboles et p = 3 positions. Les répétitions sont d'abord autorisées. La figure inventorie les 27 codes et met en évidence ceux dont les trois chiffres sont distincts.

1. Pour la première position, choisir 0, 1 ou 2 donne 3 possibilités.

2. Pour chacune d'elles, la deuxième position offre encore 3 choix, puis la troisième en offre 3. Le produit donne $3^3=3\times 3\times 3=273^3=3\backslash times3\backslash times3=27$ p-listes.

3. Si les répétitions sont interdites, il reste successivement 3, puis 2, puis 1 choix. On obtient $3\times 2\times 1=63\backslash times2\backslash times1=6$ arrangements : 012, 021, 102, 120, 201 et 210.

Le résultat est donc de 27 codes avec répétition, contre 6 sans répétition. Pour contrôler 27, regroupez les codes selon leur premier chiffre : les groupes 0, 1 et 2 contiennent chacun 9 codes.

Pour compter des codes de longueur fixe, on emploie les p-listes lorsque chaque position accepte les mêmes symboles et qu'un symbole peut revenir. Si le règlement impose des symboles tous distincts, le modèle adapté est l'arrangement sans répétition.

Pour décrire plusieurs tirages successifs avec remise, chaque résultat ordonné forme une p-liste. Sans remise, le nombre de choix diminue après chaque tirage : on passe alors à une p-liste sans répétition.

Avant tout dénombrement, deux questions tranchent le modèle : échanger deux positions change-t-il le résultat, et un élément peut-il être repris ? Si l'ordre ne compte pas, une combinaison convient mieux qu'une p-liste.

Une combinaison. Dans une p-liste, l'ordre compte : 012 et 210 sont deux résultats. Dans une combinaison, ces écritures décrivent le même choix des trois éléments.

Un arrangement. Au sens usuel, un arrangement est une p-liste sans répétition. Ainsi 001 est une 3-liste avec répétition, mais pas un arrangement de trois éléments parmi {0, 1, 2}.

Une permutation. Une permutation utilise chacun des n éléments exactement une fois : elle correspond au cas p = n sans répétition. La 2-liste 01 n'est donc pas une permutation de {0, 1, 2}.

Longueur nulle. Pour p = 0, il existe une unique 0-liste : la liste vide. La formule n⁰ donne bien 1 lorsque n est non nul.

Ensemble vide. Si n = 0 et p est strictement positif, aucune p-liste n'existe. Le cas n = 0 et p = 0 suit la convention combinatoire de l'unique liste vide.

Trop de positions sans répétition. Si p est supérieur à n, le choix se bloque après l'emploi des n éléments. Il faut conclure qu'il existe 0 arrangement, et non prolonger la formule factorielle avec (n − p)!.

Choix dépendants. La formule n^p suppose que chaque position autorise les n éléments. Si une règle interdit certains symboles selon les positions, il faut compter les choix réellement disponibles à chaque étape.

Arrangement — Approfondir le comptage des listes ordonnées lorsque chaque élément ne peut être choisi qu'une fois.

dénombrement — Situer les p-listes parmi les techniques qui comptent exactement un ensemble fini de possibilités.

Produit cartésien — Relier une p-liste avec répétition aux éléments du produit E^p.