Code de Lehmer

Définition

Le code de Lehmer, attribué à Derrick Lehmer^[1], mais connu depuis 1888 au moins^[2], associe à une permutation  σ  des éléments de l'application  ƒ=L (σ)   définie^[3] sur par

Les applications ƒ, encodant des permutations de peuvent être identifiées aux suites Comme

le code de Lehmer établit une correspondance L entre la totalité et le produit cartésien

Décodage

Un algorithme

Un algorithme simple sert à reconstituer σ à partir de ƒ=L (σ) . A titre d'exemple, le code ƒ=113252 correspond à une permutation σ telle que σ (6) =2. En effet on voit que, par définition, L (σ, n) =σ (n) . C'est le premier pas de l'algorithme :

• σ^-1=x6xxxx ;

l'avant-dernier terme de la suite ƒ, égal à L (σ, 5) =5, veut dire que parmi les 5 images envisageables pour 5, (1, 3, 4, 5, 6), il faut choisir la 5ème, σ (5) =6 :

• σ^-1=x6xxx5 ;

le terme 2=L (σ, 4) , en 4ème position de la suite ƒ, veut dire que parmi les 4 images envisageables pour 4, (1, 3, 4, 5), il faut choisir la 2ème, σ (4) =3 :

• σ^-1=x64xx5 ;

le terme 3=L (σ, 3) , en 3ème position de la suite ƒ, veut dire que parmi les 3 images envisageables pour 3, (1, 4, 5), il faut choisir σ (3) =5 :

• σ^-1=x64x35 ;

on termine avec σ (2) =1 :

• σ^-1=264x35 ;

puis σ (1) =4 :

• σ^-1=264135 ;

on a par conséquent σ= (4, 1, 5, 3, 6, 2) . Il est clair selon le déroulement de l'algorithme qu'à chaque pas il y a un choix pour σ (k) , et il n'y en a qu'un. Par conséquent chaque suite ƒ de possède un antécédent et un seul dans

Un algorithme alternatif

Une autre possibilité est de construire σ^-1 directement à partir de ƒ=113252 de la manière suivante :

• insérer 1 à la 1ère et seule place envisageable dans la suite x, ce qui donne 1,
• insérer 2 à la 1ère des places envisageables dans la suite x1x, ce qui donne 21,
• insérer 3 à la 3ème des places envisageables dans la suite x2x1x, ce qui donne 213,
• insérer 4 à la 2ème des places envisageables dans la suite x2x1x3x, ce qui donne 2413,
• insérer 5 à la 5ème des places envisageables dans la suite x2x4x1x3x, ce qui donne 24135,
• insérer 6 à la 2ème des places envisageables dans la suite x2x4x1x3x5x, ce qui donne 264135.

On peut désormais déduire σ de σ^-1. Cette construction est justifiée par l'observation suivante : par définition, ƒ (i) est le rang de σ (i) lorsque on range la suite (σ (1), σ (2), σ (3), ..., σ (i-1), σ (i) ) dans l'ordre croissant.

Applications en combinatoire et en probabilités

Indépendance des rangs relatifs

Ces applications découlent d'une propriété immédiate du code de Lehmer L (σ) vu comme suite de nombres entiers.

En d'autres termes, si on tire une permutation ω au hasard dans avec équiprobabilité (chaque permutation a une probabilité 1/n! d'être choisie), alors son code de Lehmer ƒ=L (ω) = (L (1, ω), L (2, ω), L (3, ω), ..., L (n, ω) ) est une une suite de variables aléatoires indépendantes et uniformes. L'indépendance des composantes de L résulte d'un principe général concernant les variables aléatoires uniformes sur un produit cartésien.

Nombre de records

Soit B (k) (resp. H (k) ) l'évènement "il y a record vers le bas (resp. vers le haut) au rang k", i. e. B (k) est la totalité des permutations de qui présentent un record vers le bas au rang k. On a clairement

Ainsi le nombre N_b (ω) (esp. N_h (ω) ) de records vers le bas (resp. vers le haut) de la permutation ω s'écrit comme une somme de variables de Bernoulli indépendantes de paramètres respectifs 1/k :

En effet, comme L (k) suit la loi uniforme sur

La fonction génératrice de la variable de Bernoulli est

donc la fonction génératrice de N_b est

ce qui sert à retrouver la forme produit de la série génératrice des nombres de Stirling de première espèce (non signés).

Nombre de cycles

La correspondance principale de Foata entraine que la loi de probabilité de N_b est aussi la loi du nombre de cycles de la décomposition d'une permutation tirée au hasard.

Problème des secrétaires

Il s'agit d'un problème d'arrêt optimal, classique en principe de la décision, statistiques et probabilités appliquées, où une permutation aléatoire est dévoilée progressivement à travers les premiers termes de son code de Lehmer, et où il faut s'arrêter précisément à la valeur k telle que σ (k) =n, tandis que l'unique information disponible (les k premières valeurs du code de Lehmer) ne permet pas de calculer σ (k) . En termes moins mathématiques, une série de n candidats sont présentés, l'un après l'autre, à un recruteur, qui doit recruter le meilleur, mais doit prendre sa décision ("je passe" ou "je recrute") au moment où le candidat lui est présenté, sans attendre d'avoir vu le candidat suivant (a fortiori, sans avoir vu l'ensemble des candidats). Le recruteur connait par conséquent le rang du candidat présenté en k-ème position parmi les k candidats qu'il a déjà vu, par conséquent, au moment de prendre sa k-ème décision ("je passe" ou "je recrute"), le recruteur connait les k premiers termes du code de Lehmer, tandis qu'il aurait besoin de connaître la permutation : le recruteur aurait besoin de connaître l'ensemble des termes du code de Lehmer pour prendre une décision bien informée. Pour déterminer la stratégie optimale (optimisant la probabilité de gagner), les propriétés statistiques du code de Lehmer sont principales. Johannes Kepler aurait exposé clairement le problème des secrétaires à un ami au moment où il a entrepris de choisir sa seconde femme parmi 11 épouses potentielles (choix qu'il voulait faire particulièrement méticuleusement, son premier mariage, malheureux, ayant été arrangé sans qu'il ait été consulté). ^[4]

A voir

Notes

1. ↑ (en) D. H. Lehmer, «Teaching combinatorial tricks to a computer», dans Proc. Sympos. Appl. Math. Combinatorial Analysis, Amer. Math. Soc. , vol.  10, 1960, p.  179-193 
2. ↑ voir Charles-Ange Laisant, «Sur la numération factorielle, application aux permutations», dans Bulletin de la Société Mathématique de France, vol.  16, 1888, p.  176–183 [texte intégral] , mais également (en) Don Knuth, The art of computer programming : Sorting and Searching, t.  3, Addison-Wesley, Reading, 1981, 2^e éd. , p.  12-13 , où on fait référence à un article de Marshall Hall antérieur à celui de Lehmer. C'est certainement la raison pour laquelle Don Knuth parle d'"inversion table", et non pas de "Lehmer code".
3. ↑ on utilise quelquefois une convention différente, avec des inégalités strictes plutôt que larges, en considérant le code ce qui revient à faire un décalage uniforme de 1, i. e.
4. ↑ Thomas S. Ferguson, «Who Solved the Secretary Problem?», dans Statistical Science, vol.  4, n^o 3, Août 1989, p.  282-289 [texte intégral] 

Pages liées

Permutation Nombre de Stirling Correspondance principale de Foata

Loi de Bernoulli The secretary problem Factoradic

Bibliographie

• (en) Roberto Mantaci et Fanja Rakotondrajao, «A permutation representation that knows what “Eulerian” means», dans Discrete Mathematics and Theoretical Computer Science, n^o 4, 2001, p.  101–108 [texte intégral] 
• (en) Don Knuth, The art of computer programming : Sorting and Searching, t.  3, Addison-Wesley, Reading, 1981, 2^e éd. , p.  12-13