Question

I'm working on a project that uses strings of integers with the property that the numbers 1 though N are each used twice such that each pair of numbers X are X spaces apart.

For example, in the string:

3 1 1 3 5 7 4 8 6 5 4 2 7 2 6 8

The 1's are 1 space apart, the 2's are 2 spaces apart, the 3's are 3 spaces apart, etc.

I believe I've found the number of unique such strings for the following values of N

N : # of strings

2 : 0
3 : 0
4 : 6
5 : 10
6 : 0
7 : 0
8 : 504
9 : 2656
10 : 0
11 : 0
12 : 455936

I was hoping someone could tell me if someone else has studied these patterns? And if so, could point me in the right direction?

Answer 1

What you are describing are known as Langford sequences. An Internet search will give you http://legacy.lclark.edu/~miller/langford.html and other links.

Skolem or near Skolem sequences may also be of interest to you. I have a specialization of this I am studying: see http://mathoverflow.net/questions/61744/has-anyone-seen-this-version-of-ring-toss-combinatorial-object-before .

Gerhard "Yes, Number Theory Is Involved" Paseman, 2011.07.23

Answer 2

One of the recent volumes of Knuth's "Art of Computer Programming" (maybe volume 4), has these sequences and some things like a generating function. As far as I know, the asymptotic behaviour is not known.