PI et CKPLAN

PI et CKPLAN

Bienvenue

“The methods of theoretical physics should be applicable to all those branches of thought in which the essential features are expressible with numbers.”

Paul Dirac ((from the speech at the Nobel Banquet in Stockholm, December 10, 1933)


"l'univers est nombre."
"l'univers est écrit en langage mathématique. " Galilée
Le nombre porte en lui sa dimension temporelle ET matérielle.



R.G.U. : Réalité Générale de l'Univers



et

le temps .






Et Dieu créa le nombre, comme mesure du temps, l'homme le chiffre.

Constante arithmétique (Cf constante cosmologique) :
CKPLAN=5,55382562855700000E-17



"13 chiffres significatifs, somme 66 "











Me signaler par E-Mail , ou au tel , les inepties, ou erreurs ou imprécisions, banalités, ouverture de portes ouvertes, en faisant référence au message ECRIT ou vous n’êtes pas d'accord ou dans le doute, ou dans la compréhension , et non pas à des considérations philosophiques ou littéraires, générales .



CARPE DIEM.



Rendons grâce à Dieu.


Suivez les mises à jour en inscrivant votre e-mail :

mercredi 5 mai 2021

Code de Lehmer permutohedron

 Le code de Lehmer, attribué à Derrick Lehmer1, mais connu depuis 1888 au moins2, associe à une permutation  σ  des éléments de  l'application  ƒ=L(σ)  définie3 sur  par

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

le code de Lehmer établit une correspondance L entre l'ensemble  et le produit cartésien

Décodage[modifier | modifier le code]

Propriété — Le code de Lehmer L est une bijection de  dans 

Un algorithme[modifier | modifier le code]

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 5eσ(5)=6 :

  • σ-1=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 :

  • σ-1=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 :

  • σ-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 exactement un choix pour σ(k). Donc chaque suite ƒ de  possède un antécédent et un seul dans 

Un algorithme alternatif[modifier | modifier le code]

Une autre possibilité est de construire σ-1 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 x1x, ce qui donne 21,
  • insérer 3 à la 3e des places possibles dans la suite x2x1x, ce qui donne 213,
  • insérer 4 à la 2e des places possibles dans la suite x2x1x3x, ce qui donne 2413,
  • insérer 5 à la 5e des places possibles dans la suite x2x4x1x3x, ce qui donne 24135,
  • insérer 6 à la 2e 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[modifier | modifier le code]

Indépendance des rangs relatifs[modifier | modifier le code]

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  L est une suite de variables indépendantes et uniformes ; L(i) suit la loi uniforme sur .

En d'autres termes, si on tire une permutation aléatoire ω 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 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 principe général concernant les variables aléatoires uniformes sur un produit cartésien.

Nombre de records[modifier | modifier le code]

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  qui présentent un record vers le bas au rang k. On a clairement

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 :

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 Nb est

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[modifier | modifier le code]

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.




Le permutohedron de l’ordre n n! vertices, dont chacun est adjacent à n − 1 autres. Le nombre de bords est (n − 1) n!/2, et leur longueur est 2.

Deux vertices connectés diffèrent en échangeant deux coordonnées, dont les valeurs diffèrent de 1. [3] La paire de places échangées correspond à la direction du bord. (Dans l’image de l’exemple, les vertices (3, 2, 1, 4) et (2, 3, 1, 4) sont reliées par un bord bleu et diffèrent en échangeant 2 et 3 sur les deux premières places. Les valeurs 2 et 3 diffèrent par 1. Tous les bords bleus correspondent à des swaps de coordonnées sur les deux premières places.)

Le nombre de facettes est de 2n − 2, parce qu’ils correspondent à des sous-ensembles appropriés non vides S de {1 ... n}. Les vertices d’une facette correspondant au sous-ensemble S ont en commun, que leurs coordonnées sur les endroits en S sont plus petites que les autres[4]

Bases de numération

From: To:
Result:
UnitConversion.org - the ultimate unit conversion resource.