Langford pairing

In combinatorial mathematics, a Langford pairing, also called a Langford sequence, is a permutation of the sequence of 2"n" 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". [harvtxt|Knuth|2008; harvtxt|Gardner|1978.]

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, ... OEIS|id=A014552.

These sequences are named after C. Dudley Langford, who posed the problem of constructing them in 1958. As harvtxt|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. [harvtxt|Knuth|2008.]

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

Notes

References

*citation
last = Gardner | first = Martin | authorlink = Martin Gardner
contribution = Langford's problem | page = 70
title = Mathematical Magic Show | publisher = Vintage | year = 1978.
*citation
last = Knuth | first = Donald E. | authorlink = Donald Knuth
title = The Art of Computer Programming
volume = IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions
publisher = Addison-Wesley | year = 2008 | isbn = 978-0-321-53496-5.

*citation
last = Langford | first = C. Dudley | title = Problem
journal = Mathematical Gazette | volume = 42 | year = 1958 | page = 228.
*citation
last = Nordh | first = Gustav
title = Perfect Skolem sets
year = 2005
id = arxiv | math/0506155.
*citation
last = Skolem | first = Thoralf | authorlink = Thoralf Skolem
title = On certain distributions of integers in pairs with given differences
journal = Math. Scand. | volume = 5 | year = 1957 | pages = 57–68.

External links

* [http://www.lclark.edu/~miller/langford.html Langford's Problem] , John E. Miller, 2006. With an extensive [http://www.lclark.edu/~miller/langford/langford-biblio.html bibliography] .
*mathworld | title=Langford's Problem | urlname = LangfordsProblem