3
$\begingroup$

A Langford pairing is a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which the two 1s are one unit apart, the two 2s are two units apart, and more generally the two copies of each number k are k units apart. It is well known that such pairings exist for all n = 0 or 3 (mod 4).

For all such n, is there at least one Langford pairing in which the n - 1 numbers between the two appearances of n - 1 are all different? If so, how many?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

The answer to the first question seems to be yes: there are such Langford pairings for all suitable $n$. The number of them is given by the following sequence, not yet in the OEIS:

$$0,0,1,1,0,0,3,10,0,0,76,140,0,0,2478,5454,0,0\dots$$

The 10 sequences for $n=8$ are the following:

5 8 4 1 7 1 5 4 6 3 8 2 7 3 2 6
3 6 2 7 3 2 8 5 6 4 1 7 1 5 4 8
5 8 2 3 7 2 5 3 6 4 8 1 7 1 4 6
4 6 1 7 1 4 8 5 6 2 3 7 2 5 3 8
4 2 5 7 2 4 8 6 5 3 1 7 1 3 6 8
5 2 4 7 2 8 5 4 6 3 1 7 1 3 8 6
3 1 7 1 3 8 6 4 2 5 7 2 4 6 8 5
3 1 7 1 3 8 4 5 6 2 7 4 2 5 8 6
3 1 7 1 3 5 8 6 4 2 7 5 2 4 6 8
3 1 7 1 3 6 8 5 2 4 7 2 6 5 4 8
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.