Superpermutations

1. Définitions & Propriétés

1.1 Permutations

Une permutation est un réarrangement d’éléments distincts d’un ensemble fini. Autrement dit, c’est une fonction bijective d’un ensemble fini vers lui-même. On note \mathfrak{S}_n l’ensemble des permutations d’un ensemble à n éléments vers lui-même.

Le cardinal de \mathfrak{S}_n est n!. On peut le vérifier facilement sur l'exemple suivant. Soient n verres vides et n billes distinctes (par exemple, de couleurs différentes). On souhaite placer chaque bille dans un verre qui ne peut contenir qu'une bille. La première bille peut être placée dans chacun des n verres vides, la deuxième bille peut être placée dans l'un des n-1 verres vides restants, etc. Finalement, la dernière bille ne peut être placée que dans le seul verre restant. Par principe de multiplication, le nombre de permutations est

    \[ n\times(n-1)\times(n-2)\times…\times 1 = n! . \]

Pour reprendre l'exemple de l'introduction, l'ensemble des permutations de 14 épisodes d'une série est ainsi 14!.

Dans la suite, nous allons nous servir d'alphabets et de mots sur ces alphabets pour définir rigoureusement la notion de superpermutation. Cela motive la définition suivante.

Définition — Permutation sur un alphabet. Soient n un entier naturel et \Sigma_n un alphabet de n symboles. On dit que \sigma\in\Sigma_n^* est une permutation de \Sigma_n si :

    \[ \forall x\in\Sigma_n,\quad \exists!(p,q)\in(\Sigma_n^*)^2,\quad \sigma = pxq.  \]

Autrement dit, \sigma est une permutation si tout symbole de \Sigma_n est présent exactement une fois dans \sigma. On note \mathfrak{S}(\Sigma_n) l'ensemble des permutations de \Sigma_n. Naturellement, toute permutation \sigma de \Sigma_n est de taille |\sigma| = n.

Exemple

Prenons \Sigma_3 = \{1,\,2,\,3\}. Le mot \sigma = 132 est une permutation de \Sigma_3, en revanche les mots \sigma_1=121 et \sigma_2 = 1223 ne sont pas des permutations de \Sigma_3. En effet, le symbole 3 n'est pas dans \sigma_1, et \sigma_2 comporte plus d'une fois le symbole 2.

Naturellement, les ensembles \mathfrak{S}_n et \mathfrak{S}(\Sigma_n) sont en bijection, d'où |\mathfrak{S}(\Sigma_n)| = n!.

1.2. Superpermutations

Définissons maintenant une superpermutation.

Définition — Superpermutation. Soient n un entier naturel et \Sigma_n un alphabet de n symboles. On dit qu'un mot s\in\Sigma_n^ est une superpermutation si :

    \[ \forall\sigma\in\mathfrak{S}(\Sigma_n),\quad \exists! (p,q)\in(\Sigma_n^*)^2,\quad s = p\sigma q. \]

Autrement dit, \sigma doit contenir exactement une fois toutes les permutations de \Sigma_n. On note \text{Sp}(\Sigma_n) l'ensemble des superpermutations de \Sigma_n.

On peut noter la ressemblance entre la définition d'une permutation et celle d'une superpermutation. Il s'agit essentiellement de la même définition où l'on remplace simplement l'ensemble \Sigma_n par \mathfrak{S}(\Sigma_n).

Exemple

Prenons \Sigma_2 = \{1,\,2\,\}. On a

    \[ \mathfrak{S}(\Sigma_2) = \{12,\,21\,\} \]

donc les mots 1221 et 121 sont des superpermutations de \Sigma_2. Par contre, le mot 1212 n'est pas une superpermutation de \Sigma_2. En effet, la permutation 12 y est présente deux fois. Remarquons au passage que nous venons de constater la non-unicité des superpermutations sur un alphabet donné.

Prenons à présent \Sigma_3 = \{1,\,2,\,3\}. Le mot

    \[ s = 123121321 \]

est une superpermutation de \Sigma_3. On peut le vérifier :

Il faut aussi vérifier que chacune de ces permutations n'est présente qu'une fois. C'est bien le cas ici.

Bien sûr, contrairement à l'ensemble des permutations de \Sigma_n, si n\geqslant 2, L'ensemble des superpermutations n'est pas fini. Par exemple, avec \Sigma_2 = \{1,\,2\}, tous les mots de la forme

    \[ s_n = 1\underset{n\text{ facteurs}}{\underbrace{22...22}}1 \]

sont des superpermutations. En effet, les deux permutations 12 et 21 n'y sont présentes qu'une et une seule fois : au début et à la fin du mot. Bien sûr, le mot 22 y est présent de nombreuses fois, mais ce n'est pas une permutation, donc ça ne contredit pas la définition d'une superpermutation.

L'algorithme suivant permet de déterminer si un mot est une superpermutation.

estSuperpermutation(w:string, S:string[]){
    for i from 0 to p.length() do 
        if w.numberOfOccurences(S[i]) != 1 then
            return false;
    done
    return true;
}

Il reçoit en paramètres le mot w et un tableau de string S qui contient toutes les permutations sur l'alphabet souhaité. Il s'agit donc de déterminer si chaque permutation n'est présente qu'une seule fois dans w.

1 Cliquer pour recommander cet article