How can the Langford-Skolem problem be solved?

[ramsey2879]

Bench Top's thread revived a number string curiosity that once stumped me. I wonder if anyone else saw anything like this before and can give the sequence a name.

Description
1. The sequence comprises only numbers from 1 to 2n.
2. Each number from 1 to 2n appears once and only once.
3. For i = 1 to n, the 2i(th) number minus the 2i-1(th) number is i.

examples

a)for n = 1 the sequence is <1,2>
b)there are no valid sequences for n = 2 or 3
c)for n = 4 one valid sequence and its cousin is <2,3,6,8,4,7,1,5>/<6,7,1,3,2,5,4,8>. The cousin of a sequence is found by letting each 2i-1(th) number of the new sequence be equal to 2n +1 minus the 2i(th) number of the first sequence.

There are sequences for even larger n but they are not readily available to me.

The questions which stumped me are:
1. Is there a rule for which values n can take?
2. Is there an algorithm for determining a valid sequence?
3. Is there a rule for determining how many valid sequences there are for a given n?

Does anyone have any thoughts on this?

 

[ramsey2879]

Following is verbatum of a message I got. Very interesting. My sequence appears related to a Skolem Type sequence in which the Ai - Bi differ by i, not the closely related Langford Type sequence in which the Ai - Bi differ by i+1:
"Hello Ramsey.

I started my Google search by looking for

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

(2,3)(6,8)(4,7)(1,5) represents a Langford sequence as follows:

1 2 3 4 5 6 7 8
Place 1 in positions 2 and 3

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

Place 2 in positions 6 and 8

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

Place 3 in positions 4 and 7

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

Place 4 in positions 1 and 5

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

Langford sequence


http://www.springerlink.com/content/w037672q726x9984/

Abstract
Let D be a set of positive integers. A Skolem-type sequence is a
sequence of i ∈ D such that every i ∈ D appears exactly twice in the
sequence at positions a i and b i , and |b i − a i | = i. These
sequences might contain empty positions, which are filled with null
elements. Thoralf A. Skolem defined and studied Skolem sequences in
order to generate solutions to Heffter’s difference problems. Later,
Skolem sequences were generalized in many ways to suit constructions of
different combinatorial designs. Alexander Rosa made the use of these
generalizations into a fine art. Here we give a survey of Skolem-type
sequences and their applications.

Keywords Skolem sequence - Langford sequence - design theory - triple
systems - graph labeling - γ coverings

http://en.wikipedia.org/wiki/Langford_pairing

Langford pairing
From Wikipedia, the free encyclopedia
Jump to: navigation, search
A Langford pairing for n = 4.

In combinatorial mathematics, a Langford pairing, also called a Langford
sequence, is a permutation of the sequence of 2n numbers 1, 1, 2, 2,
..., n, n in which the two ones are one unit apart, the two twos are two
units apart, and more generally the two copies of each number k are k
units apart. For example, a Langford pairing for n = 3 is given by the
sequence 2,3,1,2,1,3. Langford's problem is the task of finding Langford
pairings for a given value of n.[1]

Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for
instance, there is no Langford pairing when n = 5. The numbers of
different Langford pairings, for n starting from 3, counting any
sequence as being the same as its reversal, are

1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, ... (sequence A014552 in
OEIS).

These sequences are named after C. Dudley Langford, who posed the
problem of constructing them in 1958. As Knuth (2008) describes, the
problem of listing all Langford pairings for a given n can be solved as
an instance of the exact cover problem, but for large n the number of
solutions can be calculated more efficiently by algebraic methods. In
the 1960s, E.J. Groth used these sequences to construct circuits for
integer multiplication.[2]

The closely related concept of a Skolem sequence[3] is defined in the
same way, but instead permutes the sequence 0, 0, 1, 1, ..., n − 1, n −
1. Skolem (1957) used these sequences to construct Steiner triple systems.

http://oeis.org/A014552

A014552 Number of solutions to Langford (or Langford-Skolem) problem. 6
0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640,
326721800, 0, 0, 256814891280, 2636337861200, 0, 0, 3799455942515488,
46845158056515936 (list; graph; listen; history; internal format)
OFFSET

1,7
COMMENTS

How many ways are of arranging the numbers 1,1,2,2,3,3,...,n,n so that
there is one number between the two 1's, two numbers between the two
2's, ..., n numbers between the two n's?"