Suite de Skolem

Modèle:Redirect En mathématiques, une suite de Skolem d’ordre $n$, du nom du mathématicien norvégien Thoralf Skolem qui les a étudiées en 1957 , est une suite finie de $2n$ entiers, constituée des entiers de 1 à $n$ répétés chacun deux fois, les deux occurrences d'un entier $k$ étant distantes de $k$.

Une suite de Langford, du nom de C. Dudley Langford qui a posé le problème de leur construction en 1958, en est la variante où les occurrences de $k$ sont distantes de $k+1$ (autrement dit il y a $k$ nombres entre les deux occurrences de $k$).

Par exemple, (4,2,3,2,4,3,1,1) est une suite de Skolem d’ordre 4 et (2,3,1,2,1,3) une suite de Langford d'ordre 3.

Définition formelle

Une suite de Skolem est de la forme $(k_1,\cdots ,k_{2n})$, avec :

• pour tout $k$ de l’ensemble $\{1,2,3,\dots ,n\}$, il y a exactement deux indices $i$ et $j$ pour lesquels $k_i=k_j=k$ ;
• si $k_i=k_j=k$ avec $i<j$ alors $j-i=k$.

La suite des $k_i-1$ possède alors la même propriété qu'une suite de Langford (il y a $k$ nombres entre les deux occurrences de $k$), mais cette suite prend ses valeurs de 0 à $n-1$ (tandis qu'une suite de Langford prend ses valeurs de 1 à $n$) ; par exemple, la suite de Skolem (4,2,3,2,4,3,1,1) donne la suite de Langford "étendue" (3,1,2,1,3,2,0,0).

Propriétés

Il existe une suite de Skolem d’ordre $n$ ssi $n$ est congru à 0 ou 1 modulo 4. Modèle:Refsou

La restriction analogue pour les suites de Langford est : $n$ congru à 0 ou 3 modulo 4.

Dénombrements et exemples

On ne connait pas de formule générale donnant le nombre de suites de Skolem ou de Langford d'ordre $n$, mais seulement des algorithmes pour les énumérer.

Les premiers termes de la suite formée des nombres de suites de Langford d'ordre $n$ (en commençant par n = 1 et en comptant pour 1 deux suites inversées l'une de l'autre) sont :

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, voir la Modèle:OEIS.

La même suite pour les suites de Skolem débute par : 1, 0, 0, 3, 5, 0, 0, 252, 1318, 0, 0, 227968, 1520280, voir la Modèle:OEIS où les suites de Skolem sont dénommées suites de Nickerson.

Par exemple :

• la seule suite de Langford d'ordre 4 est (2,3,4,2,1,3,1,4) ou son inverse, et l'une des 26 suites de Langford d'ordre 7 est (1,4,1,5,6,7,4,2,3,5,2,6,3,7) ;
• l'une des 5 suites de Skolem d'ordre 5 est (4,5,1,1,4,3,5,2,3,2).

Variantes

Éric Angelini appelle nombre de Skolem-langford un entier naturel dont les chiffres de l'écriture décimale sont répétés exactement deux fois et tels qu'il y a $k$ chiffres entre les deux occurrences d'un chiffre $k$. Rangés dans l'ordre croissant, ces nombres sont : 2002, 131003, 231213, 300131, 312132, 420024,... Il y en a exactement 20120, et le plus grand d'entre eux est 978416154798652002 ; voir la Modèle:OEIS.

En faisant une recherche sur Skolem Langford dans l'OEIS, on trouvera plusieurs autres variantes.

Dans la culture

Les suites de Skolem ont inspiré une bande dessinée de Jean-François Kierzkowski (2015 et 2016).

La suite de Langford d'ordre 8 est à la base de Pyramids XXV, une œuvre du peintre allemand Gerhard Hotter.

Voir aussi

Bibliographie

• Modèle:Article

Articles connexes

• Suite de Kolakoski