Code de Lehmer

Code de Lehmer
Page d'aide sur l'homonymie Pour les articles homonymes, voir Lehmer.

Sommaire

Définition

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

f(i)=\text{Card}\left\{j\ |\ 1\le j\le i\text{ et }\sigma(j)\le\sigma(i)\right\}=L(\sigma,i).

Les applications ƒ, encodant des permutations de \scriptstyle\ \mathfrak{S}_n,\ peuvent être identifiées aux suites \scriptstyle\ \left(f(i)\right)_{1\le i\le n}.\ Comme

1\le f(i)\le i,

le code de Lehmer établit une correspondance L entre l'ensemble \scriptstyle\ \mathfrak{S}_n\ et le produit cartésien

[\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!].

Décodage

Propriété — Le code de Lehmer L est une bijection de \scriptstyle\ \mathfrak{S}_n\ dans \scriptstyle\ [\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!].

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 :

  • σ-1=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 5ème, σ(5)=6 :

  • σ-1=x6xxx5 ;

le terme 2=L(σ,4), en 4ème position de la suite ƒ, signifie que parmi les 4 images possibles 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 ƒ, signifie que parmi les 3 images possibles 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 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 un choix pour σ(k), et il n'y en a qu'un. Donc chaque suite ƒ de \scriptstyle\ [\![1,1]\!]\times[\![1,2]\!]\times[\![1,3]\!]\times\dots\times[\![1,n]\!]\ possède un antécédent et un seul dans \scriptstyle\ \mathfrak{S}_n.

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 possible dans la suite x, ce qui donne 1,
  • insérer 2 à la 1ère des places possibles dans la suite x1x, ce qui donne 21,
  • insérer 3 à la 3ème des places possibles dans la suite x2x1x, ce qui donne 213,
  • insérer 4 à la 2ème des places possibles dans la suite x2x1x3x, ce qui donne 2413,
  • insérer 5 à la 5ème des places possibles dans la suite x2x4x1x3x, ce qui donne 24135,
  • insérer 6 à la 2ème des places possibles dans la suite x2x4x1x3x5x, ce qui donne 264135.

On peut maintenant déduire σ de σ-1. 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.

Propriété — Sous la loi uniforme sur \scriptstyle\ \mathfrak{S}_n,\ L est une suite de variables indépendantes et uniformes ; L(i) suit la loi uniforme sur \scriptstyle\ [\![1,i]\!]\ .

En d'autres termes, si on tire une permutation ω au hasard dans \scriptstyle\ \mathfrak{S}_n,\ 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. 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

Définition — Dans une suite u=(uk)1≤k≤n, il y a record vers le bas (resp. vers le haut) au rang k si uk est strictement plus petit (resp. strictement plus grand) que chaque terme ui tel que i<k.

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 l'ensemble des permutations de \scriptstyle\ \mathfrak{S}_n\ qui présentent un record vers le bas au rang k. On a clairement

\{\omega\in B(k)\}\Leftrightarrow\{L(k,\omega)=1\}\quad\text{et}\quad\{\omega\in H(k)\}\Leftrightarrow\{L(k,\omega)=k\}.

Ainsi le nombre Nb(ω) (esp. Nh(ω)) 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 :

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)}.

En effet, comme L(k) suit la loi uniforme sur \scriptstyle\ [\![1,k]\!],\

\mathbb{P}(B(k))=\mathbb{P}(L(k)=1)=\mathbb{P}(H(k))=\mathbb{P}(L(k)=k)=\tfrac1k.

La fonction génératrice de la variable de Bernoulli 1\!\!1_{B(k)} est

G_k(s)=\frac{k-1+s}k,

donc la fonction génératrice de Nb est

G(s)=\prod_{k=1}^nG_k(s)\ =\ \frac{(s)_{\uparrow n}}{n!},

ce qui permet de 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 fondamentale de Foata entraine que la loi de probabilité de Nb 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 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à vu, 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 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 aussi (en) Don Knuth, The art of computer programming : Sorting and Searching, t. 3, Reading, Addison-Wesley, 1981, 2e éd., p. 12-13 , où on fait référence à un article de Marshall Hall antérieur à celui de Lehmer. C'est probablement la raison pour laquelle Don Knuth parle d'"inversion table", et non pas de "Lehmer code".
  3. on utilise parfois une convention différente, avec des inégalités strictes plutôt que larges, en considérant le code \scriptstyle \ \tilde{f}(i)=\text{Card}\left\{j\ |\ 1\le j<i\text{ et }\sigma(j)<\sigma(i)\right\}, ce qui revient à faire un décalage uniforme de 1, i.e. \scriptstyle \ \tilde{f}(i)=f(i)-1,\quad\forall i.
  4. Thomas S. Ferguson, « Who Solved the Secretary Problem? », dans Statistical Science, vol. 4, no 3, août 1989, p. 282-289 [texte intégral] 

Pages liées

Bibliographie

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Code de Lehmer de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Lehmer — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Lehmer: Derrick Henry Lehmer (1905 1991) Code de Lehmer Conjecture de Lehmer (en) Problème de Lehmer …   Wikipédia en Français

  • Code pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • Lehmer mean — The Lehmer mean of a tuple x of positive real numbers is defined as::L p(x) = frac{sum {k=1}^{n} x k^p}{sum {k=1}^{n} x k^{p 1.The Weighted Lehmer mean with respect to a tuple w of positive weights is defined as::L {p,w}(x) = frac{sum {k=1}^{n} w …   Wikipedia

  • Derrick Lehmer — Pour les articles homonymes, voir Lehmer. Derrick Henry Lehmer (23 février 1905 – 22 mai 1991) est un mathématicien américain, inventeur d un test de primalité. Il a aussi posé le problème qui porte son nom : si n ≡ 1 mod φ(n), n est il… …   Wikipédia en Français

  • Derrick Henry Lehmer — Born February 23, 1905(1905 02 23) Berkeley, California Died May 22, 1991(1991 05 22) (aged&# …   Wikipedia

  • Derrick Lehmer — Derrick Henry Lehmer (* 23. Februar 1905 in Berkeley (Kalifornien); † 22. Mai 1991 ebenda) war ein US amerikanischer Mathematiker, spezialisiert auf Zahlentheorie. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften …   Deutsch Wikipedia

  • Derrick Norman Lehmer — Born July 27, 1867(1867 07 27) Somerset, Indiana, United States Died September 8, 1938(1938 09 08) Berkeley, California, United States Education …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Loi de Bernoulli — Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Paramètres (nombre réel) Support …   Wikipédia en Français

  • Nombre de Stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”