Langford pairing

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

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

Properties

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

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

• Stirling permutation, a different type of permutation of the same multiset

Notes

1. Knuth (2008); Gardner (1978).
2. Nordh (2008)
3. Knuth (2008).

References

• Gardner, Martin (1978), "Langford's problem", Mathematical Magic Show, Vintage, p. 70.
• Knuth, Donald E. (2008), The Art of Computer Programming, Vol. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley, ISBN 978-0-321-53496-5.
• Langford, C. Dudley (1958), "Problem", Mathematical Gazette 42: 228.
• Nordh, Gustav (2008), "Perfect Skolem sets", Discrete Mathematics 308 (9): 1653–1664, arXiv:math/0506155, doi:10.1016/j.disc.2006.12.003, MR 2392605.
• Skolem, Thoralf (1957), "On certain distributions of integers in pairs with given differences", Mathematica Scandinavica 5: 57–68, MR 0092797.

External links

• John E. Miller, Langford's Problem, 2006. (with an extensive bibliography).
• Weisstein, Eric W., "Langford's Problem", MathWorld.