Voir la source de Code de Lehmer

{{voir homonymie|Lehmer}}

Le '''code de Lehmer''' est un concept mathématique, en [[combinatoire]].

== Définition ==
Le code de Lehmer, attribué à [[Derrick Lehmer]]<ref>{{Article
|langue=en
|prénom1=D.H.
|nom1=Lehmer
|titre=Teaching combinatorial tricks to a computer
|périodique=Proc. Sympos. Appl. Math. Combinatorial Analysis, Amer. Math. Soc.
|année=1960
|volume=10
|numéro=
|pages=179-193
}}</ref>, mais connu depuis 1888 au moins<ref>voir {{Article|langue=fr
|prénom1=Charles-Ange
|nom1=Laisant
|lien auteur1=Charles-Ange Laisant
|titre=Sur la numération factorielle, application aux permutations
|périodique=Bulletin de la Société Mathématique de France
|année=1888
|volume=16
|pages=176-183
|url texte=http://www.numdam.org/item?id=BSMF_1888__16__176_0
}}, mais aussi {{Ouvrage
|langue=en
|prénom1=Don
|nom1=Knuth
|lien auteur1=Donald Knuth
|titre=The art of computer programming
|sous-titre=Sorting and Searching
|tome=3
|éditeur=Addison-Wesley
|lieu=Reading
|année=1981
|numéro d'édition=2
|passage=12-13
|isbn=
}}, où on fait référence à un article de Marshall Hall antérieur à celui de Lehmer. C'est probablement la raison pour laquelle [[Donald Knuth|Don Knuth]] parle d'"inversion table", et non pas de "Lehmer code".</ref>, associe à une [[permutation]] ''&nbsp;σ&nbsp;''  des éléments de <math display=inline> [\![1,n]\!]\ </math> l'application &nbsp;''ƒ''=''L''(''σ'') définie<ref>on utilise parfois une convention différente, avec des inégalités strictes plutôt que larges, en considérant le code <math display=inline> \tilde{f}(i)=\text{Card}\left\{j\ |\ 1\le j<i\text{ et }\sigma(j)<\sigma(i)\right\},</math> ce qui revient à faire un décalage uniforme de 1, i.e. <math display=inline> \tilde{f}(i)=f(i)-1,\quad\forall i.</math></ref> sur  <math display=inline> [\![1,n]\!]\ </math> par 
<center><math>f(i)=\text{Card}\left\{j\ |\ 1\le j\le i\text{ et }\sigma(j)\le\sigma(i)\right\}=L(\sigma,i).</math></center>
Les applications ''ƒ'', encodant des permutations de <math display="inline"> \mathfrak{S}_n,\ </math> peuvent être identifiées aux suites <math display="inline"> \left(f(i)\right)_{1\le i\le n}.\ </math> Comme
<center><math>1\le f(i)\le i,</math></center>
le code de Lehmer établit une correspondance ''L'' entre l'ensemble  <math display="inline"> \mathfrak{S}_n\ </math>  et le produit cartésien 
<center><math>[\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!].</math></center>

==Décodage==
{{Théorème|Propriété|Le code de Lehmer ''L'' est une bijection de <math display="inline"> \mathfrak{S}_n\ </math>  dans
<math display="inline"> [\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!].</math>}}

===Un algorithme===
Un algorithme simple permet de reconstituer ''σ'' à partir de ''ƒ''=''L''(''σ''). Par 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 :
* ''σ''<sup>-1</sup>=x6xxxx ;
l'avant-dernier terme de la suite  ''ƒ'', égal à ''L''(''σ'',5)=5, signifie que parmi les 5 images possibles pour 5, (1,3,4,5,6), il faut choisir la {{5e}}, ''σ''(5)=6 :
* ''σ''<sup>-1</sup>=x6xxx5 ;
le terme 2=''L''(''σ'',4), en {{4e|position}} de la suite ''ƒ'', signifie que parmi les 4 images possibles pour 4, (1,3,4,5), il faut choisir la {{2e}}, ''σ''(4)=3 :
* ''σ''<sup>-1</sup>=x64xx5 ;
le terme 3=''L''(''σ'',3), en {{3e|position}} de la suite ''ƒ'', signifie que parmi les 3 images possibles pour 3, (1,4,5), il faut choisir ''σ''(3)=5 :
* ''σ''<sup>-1</sup>=x64x35 ;
on termine avec ''σ''(2)=1 :
* ''σ''<sup>-1</sup>=264x35 ;
puis ''σ''(1)=4 :
* ''σ''<sup>-1</sup>=264135'' ;
on a donc ''σ''=(4,1,5,3,6,2). Il est clair d'après le déroulement de l'algorithme qu'à chaque pas, il y a exactement un choix pour ''σ''(''k''). Donc chaque suite  ''ƒ'' de <math display="inline"> [\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!]\ </math> possède un antécédent et un seul dans <math display="inline"> \mathfrak{S}_n.</math>

===Un algorithme alternatif===
Une autre possibilité est de construire ''σ''<sup>-1</sup> directement à partir de ''ƒ''=113252 de la manière suivante :
*insérer 1 à la {{1re}} et seule place possible dans la suite ''x'', ce qui donne 1,
*insérer 2 à la {{1re}} des places possibles dans la suite ''x''1''x'', ce qui donne 21,
*insérer 3 à la {{3e}} des places possibles dans la suite ''x''2''x''1''x'', ce qui donne 213,
*insérer 4 à la {{2e}} des places possibles dans la suite ''x''2''x''1''x''3''x'', ce qui donne 2413,
*insérer 5 à la {{5e}} des places possibles dans la suite ''x''2''x''4''x''1''x''3''x'', ce qui donne 24135,
*insérer 6 à la {{2e}} des places possibles dans la suite ''x''2''x''4''x''1''x''3''x''5''x'', ce qui donne 264135.
On peut maintenant déduire ''σ'' de ''σ''<sup>-1</sup>. Cette construction est justifiée par l'observation suivante : par définition, ''ƒ''(''i'') est le rang de ''σ''(''i'') quand 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.
{{Théorème|Propriété|Sous la loi uniforme sur <math display=inline> \mathfrak{S}_n,\ </math> ''L'' est une suite de variables [[Indépendance (probabilités)|indépendantes]] et uniformes ; ''L''(''i'') suit la [[Loi uniforme discrète|loi uniforme]] sur <math display=inline>[\![1,i]\!]\ </math>.}}

En d'autres termes, si on tire une [[permutation aléatoire]] ''ω'' au hasard dans <math display=inline>\mathfrak{S}_n,\ </math> 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 suite de variables aléatoires indépendantes et uniformes. Cela contraste avec le comportement probabiliste de la suite (''ω''(1), ''ω''(2), ''ω''(3), ... , ''ω''(''n''))  des images des entiers par la permutation aléatoire ''ω'', qui fournit la description la plus naturelle de  ''ω'', mais qui est une suite de variables aléatoires  ''dépendantes'', donc moins maniable pour effectuer des calculs de probabilités. L'indépendance des composantes de ''L'' résulte d'un [[Indépendance (probabilités)#Cas des variables discrètes|principe général]] concernant les variables aléatoires [[Loi uniforme discrète|uniformes]] sur un [[produit cartésien]].

===Nombre de records===
{{Théorème|Définition|Dans une suite ''u''{{=}}(''u<sub>k</sub>'')<sub>1≤''k''≤''n''</sub>, il y a '''''record vers le bas''''' (resp. '''''vers le haut''''') au rang ''k'' si ''u<sub>k</sub>''  est strictement plus petit (resp. strictement plus grand) que chaque terme ''u<sub>i</sub>'' tel que ''i''<''k''.}}

Soit ''B''(''k'') (resp. ''H''(''k'')) l'évènement "il y a [[Loi de Bernoulli#Nombre de records et nombre de cycles des permutations|record vers le bas]] (resp. vers le haut) au rang ''k''" , i.e. ''B''(''k'') est l'ensemble des permutations de <math display=inline>\mathfrak{S}_n\ </math> qui présentent un record vers le bas au rang ''k''. On a clairement
<center><math>\{\omega\in B(k)\}\Leftrightarrow\{L(k,\omega)=1\}\quad\text{et}\quad\{\omega\in H(k)\}\Leftrightarrow\{L(k,\omega)=k\}.</math></center>
Ainsi le nombre ''N<sub>b</sub>''(''ω'') (esp. ''N<sub>h</sub>''(''ω'')) de records vers le bas (resp. vers le haut) de la permutation ''ω'' s'écrit comme une [[Loi de Bernoulli#Applications au comptage|somme de variables de Bernoulli]] indépendantes de paramètres respectifs 1/''k'' :
<center><math>N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{B(k)}\quad\text{et}\quad N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{H(k)}.</math></center>
En effet, comme ''L''(''k'') suit la loi uniforme sur <math display=inline>[\![1,k]\!],\ </math> 
<center><math>\mathbb{P}(B(k))=\mathbb{P}(L(k)=1)=\mathbb{P}(H(k))=\mathbb{P}(L(k)=k)=\tfrac1k.</math></center>
La [[fonction génératrice]] de la [[Loi de Bernoulli|variable de Bernoulli]] <math>1\!\!1_{B(k)}</math> est 
<center><math>G_k(s)=\frac{k-1+s}k,</math></center>
[[Fonction génératrice des probabilités#Propriétés|donc]] la fonction génératrice de ''N<sub>b</sub>'' est
<center><math>G(s)=\prod_{k=1}^nG_k(s)\ =\ \frac{(s)_{\uparrow n}}{n!},</math></center>
ce qui permet de retrouver la forme produit de la série génératrice des [[Nombre de Stirling#Nombre de Stirling de première espèce|nombres de Stirling de première espèce]] (non signés).

===Nombre de cycles===
La [[correspondance fondamentale de Foata]] entraîne que la loi de probabilité de ''N<sub>b</sub>'' est aussi la loi du nombre de cycles de la décomposition d'une permutation tirée au hasard.

===Problème des secrétaires===
Le [[problème des secrétaires]] est un problème d'arrêt optimal, classique en théorie 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 exactement à la valeur ''k'' telle que ''σ''(''k'')=''n'', alors que la seule 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 tous les candidats). Le recruteur connait donc le rang du candidat présenté en ''k''-ème position parmi les ''k'' candidats qu'il a déjà vus, donc, 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, alors qu'il aurait besoin de connaître la permutation : le recruteur aurait besoin de connaître tous les 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 cruciales. [[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 très méticuleusement, son premier mariage, malheureux, ayant été arrangé sans qu'il eût été consulté)<ref>{{Article
|langue=en
|prénom1=Thomas S.
|nom1=Ferguson
|lien auteur1=
|titre=Who Solved the Secretary Problem?
|périodique=Statistical Science
|lien périodique=
|jour=
|mois=Août
|année=1989
|volume=4
|numéro=3
|pages=282-289         
|issn=
|url texte=https://www.jstor.org/stable/2245639
}}</ref>.

==Notes et références==
<references/>

==Voir aussi==

===Article connexe===
{{Lien|trad=Factorial number system|Numération factorielle}}

===Bibliographie===
*{{Article
|langue=en
|prénom1=Roberto
|nom1=Mantaci
|prénom2=Fanja
|nom2=Rakotondrajao
|titre=A permutation representation that knows what “Eulerian” means
|périodique=Discrete Mathematics and Theoretical Computer Science
|année=2001
|numéro=4
|pages=101-108
|url texte=http://www.dmtcs.org/volumes/abstracts/pspapers/dm040203.ps
}}
*{{Ouvrage
|langue=en
|prénom1=M.
|nom1=Lothaire
|lien auteur1=M. Lothaire
|titre=Algebraic combinatorics on words
|éditeur=[[Cambridge University Press|CUP]]
|lieu=Cambridge
|année=2002
|passage=372-375
|isbn=
}}

{{Portail|probabilités et statistiques}}

[[Catégorie:Combinatoire]]
[[Catégorie:Probabilités]]