8
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For such things the "The On-Line Encyclopedia of Integer Sequences" is really handy, it gives this result for your sequence: oeis.org/A004075 $\endgroup$
    – Marcel Bischoff
    Commented Aug 11, 2011 at 18:03

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Your first link fails to open. Do you happen to have an updated link or does that page not exist anymore? $\endgroup$
    – Martin R
    Commented Feb 20, 2020 at 15:47
  • $\begingroup$ @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. $\endgroup$
    – Gerhard Paseman
    Commented Feb 20, 2020 at 18:16
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Welcome back to MathOverflow! Gerhard "Apologies For Missing You Before" Paseman, 2011.08.11 $\endgroup$
    – Gerhard Paseman
    Commented Aug 11, 2011 at 7:31
  • $\begingroup$ 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".) $\endgroup$
    – shreevatsa
    Commented Oct 16, 2016 at 9:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .