Langford pairing
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 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. 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]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, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200, 0, 0, … (sequence A014552 in the 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]- Stirling permutation, a different type of permutation of the same multiset
Notes
[edit]References
[edit]- 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, doi:10.2307/3610395, JSTOR 3610395.
- 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, doi:10.7146/math.scand.a-10490, MR 0092797.
External links
[edit]- John E. Miller, Langford's Problem, 2006. (with an extensive bibliography).
- Weisstein, Eric W. "Langford's Problem". MathWorld.