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. Langford pairings are named after C. Dudley Langford, who posed the problem of constructing them in 1958.

Langford's problem is the task of finding Langford pairings for a given value of n.[1]

The closely related concept of a Skolem sequence[2] is defined in the same way, but instead permutes the sequence 0, 0, 1, 1, ..., n − 1, n − 1.

Example[edit]

For example, a Langford pairing for n = 3 is given by the sequence 2,3,1,2,1,3.

Properties[edit]

Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when n = 1, 2, or 5.

The numbers of different Langford pairings for n = 1, 2, …, counting any sequence as being the same as its reversal, are

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

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.

Applications[edit]

Skolem (1957) used Skolem sequences to construct Steiner triple systems.

In the 1960s, E. J. Groth used Langford pairings to construct circuits for integer multiplication.[3]

See also[edit]

Notes[edit]

References[edit]

External links[edit]