combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a Langford pairing, also called a Langford sequence, is a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...

of the sequence of 2''n'' 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''. The closely related concept of a Skolem sequence is defined in the same way, but instead permutes the sequence 0, 0, 1, 1, ..., ''n'' − 1, ''n'' − 1.

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 Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In mod ...

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, … . As describes, the problem of listing all Langford pairings for a given ''n'' can be solved as an instance of the

exact cover problem In the mathematical field of combinatorics, given a collection of subsets of a Set (mathematics), set , an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a partition ...

, but for large ''n'' the number of solutions can be calculated more efficiently by algebraic methods.

Applications

used Skolem sequences to construct

Steiner triple system 250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...

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

multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...

Notes

References

*. *. *. *. *.

External links