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

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

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

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

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 modu ...

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 \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that e ...

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

Applications

used Skolem sequences to construct Steiner triple systems. In the 1960s, E. J. Groth used Langford pairings to construct circuits for integer

multiplication Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...

Notes

References

*. *. *. *. *.

External links