Numéroter les permutations
Quelqu'un connaîtrait-il une bijection simple entre les permutations à 5 éléments et les entiers de 1 à 120. Par simple, j'entends calculable de tête en quelques secondes. Exemple : on donne (1 5 4 2 3) et on retourne rapidement l'entier associé. J'en ai une sous le coude mais peut-être en existe-t-il de bien connues ? Merci d'avance !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Poser (pour $\sigma$ permutation de {1,...,n})
$$N(\sigma)=\sum_{i=1}^n \frac{n!}{i!}\,k_i(\sigma)= k_n(\sigma) + n (k_{n-1}(\sigma)+(n-1)(k_{n-2}(\sigma)+\cdots)).$$
Ca numérote entre 0 et n!-1.
On pourrait définir un ordre croissant parmi ces permutations:
12345 - 12354 - 12435 - 12453 - 12523 -...
et créer une espèce de base de Zeckendorf
avec 2! 3! 4!
ainsi, le 25143 occuperait le rang $4!+3*3!+1*2!=24+18+2=46$
et la 100e permutation serait obtenue par
$100=4*4!+0*3!+2*2!$
donc $p_{100}=41352$
Ce n'est qu'une idée, je ne suis pas du tout spécialiste de ces questions et n'ai découvert l numération de Zeckendorf qu'à l'occasion d'un fil récent
Je ne suis même pas sûr de la justesse de mes calculs...:S
[Edit:effectivement, la détermination de P100 est fausse. voir ci-dessous]
Ça m'obligera à mettre mes idées au clair
Classer les perutations en ordre croissant suivant l'écriture décimale
Je note Po=12345
Pour trouver le rang de 25143,
Je regarde le 1er chiffre. Ce n'est pas 1, donc il y a déjà au moins 4! Permutations qui précèdent
Le 2e chiffre est 5 donc il y a au moins 3*3! De plus qui précèdent.( ce n'est ni 1, ni 3, ni 4)
Le 3e chiffre est 1, il est le plus petit des non utilisés.
Le 4e n'est pas 3, donc il faut encore ajouter 1(!?) permutation.
Ainsi le Rang de 25143 est 4!+ 3*3!+ 1=43
Réciproquement, la permutation de rang 100=4*4!+0*3!+2*2!+0,
donc p100=51423
Est-ce plus clair, Ga?
Amicalement. jacquot
Il est possible que ma numérotation n'apporte rien de plus que celle de LtDrogo.
Tout au plus m'aura-t-elle permis de comprendre le problème.:S