# Integer strings such as: 4,1,1,3,4,2,3,2

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?

• For such things the "The On-Line Encyclopedia of Integer Sequences" is really handy, it gives this result for your sequence: oeis.org/A004075 Aug 11, 2011 at 18:03

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.

(According to the Internet Archive that page has moved to http://dialectrix.com/langford.html).

Skolem or near Skolem sequences may also be of interest to you. I have a specialization of this I am studying: see Has anyone seen this version of ring toss (combinatorial object) before? .

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

• Your first link fails to open. Do you happen to have an updated link or does that page not exist anymore? Feb 20, 2020 at 15:47
• @Martin R, you might be able to recover the page from the internet archive. (Martin Sleziak might come by and provide the link for us.) If you search and find a better page, I invite you to add a new link as part of a new paragraph in between the first two paragraphs of this answer post. Gerhard "Collaborative Post Editing Is Encouraged" Paseman, 2020.02.20. Feb 20, 2020 at 18:16

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.

• Welcome back to MathOverflow! Gerhard "Apologies For Missing You Before" Paseman, 2011.08.11 Aug 11, 2011 at 7:31
• Indeed it's present in Knuth: the very first paragraph of Volume 4A mentions this ("Langford pairs") as an example of combinatorics, and already on page 2 he points out they exist only when when $n = 4m - 1$ or $n = 4m$, and that the number of essentially different pairings $L_n$ "might be roughly of order $(4n/e^3)^{n+1/2}$ when it is nonzero (see exercise 5); and in fact this prediction turns out to be basically correct in all known cases." (His $L_n$ numbers are smaller than the OPs, presumably because of differing definitions of "essentially different".) Oct 16, 2016 at 9:16