Suite de Skolem

Une suite de Skolem d’ordre n est une suite 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 en est la variante où les occurrences de k sont distantes de k+1.

Plus formellement, une suite de Skolem est de la forme (S₁, … , S_2n ), avec :

• pour chaque k dans l’ensemble {1,2,3, … , n}, il y a exactement deux indices i et j pour lesquels S_i = S_j = k ;
• si S_i = S_j = k avec i < j alors j - i = k.

La suite des S_i - 1 possède alors la même propriété qu'une suite de Langford (les deux occurrences de k y sont distantes de k + 1), mais cette suite prend ses valeurs de 0 à n - 1 (tandis qu'une suite de Langford prend ses valeurs de 1 à n ).

Par exemple, 4,2,3,2,4,3,1,1 est une suite de Skolem d’ordre 4.

Il n’existe de suite(s) de Skolem d’ordre n que si n est congru à 0 ou 1 modulo 4[1]. (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[2] est : n congru à 0 ou 3 modulo 4.

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

Les suites de Skolem ont été décrites par le mathématicien norvégien Thoralf Skolem.