Suite de Skolem

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

Une suite de Langford, du nom de C. Dudley Langford qui a posé le problème de leur construction en 1958^[2], en est la variante où les occurrences de ${\displaystyle k}$ sont distantes de ${\displaystyle k+1}$ (autrement dit il y a ${\displaystyle k}$ nombres entre les deux occurrences de ${\displaystyle 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 ${\displaystyle (k_{1},\cdots ,k_{2n})}$, avec :

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

La suite des ${\displaystyle k_{i}-1}$ possède alors la même propriété qu'une suite de Langford (il y a ${\displaystyle k}$ nombres entre les deux occurrences de ${\displaystyle k}$), mais cette suite prend ses valeurs de 0 à ${\displaystyle n-1}$ (tandis qu'une suite de Langford prend ses valeurs de 1 à ${\displaystyle 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 ${\displaystyle n}$ ssi ${\displaystyle n}$ est congru à 0 ou 1 modulo 4^[3]. (Cette restriction tombe dans le cas des "suites de Skolem étendues", comprenant en plus l'entier 0.)^{[réf. souhaitée]}

La restriction analogue pour les suites de Langford^[4] est : ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 suite A014552 de l'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^[3], voir la suite A059106 de l'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)^[3].

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 ${\displaystyle k}$ chiffres entre les deux occurrences d'un chiffre ${\displaystyle k}$^[5]. 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 suite A108116 de l'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)^[6].

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