science

Langford pairing

Langford pairing is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Langford pairing rather than just read about it. In short: 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.

Key takeaways

Langford pairing belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Langford pairing to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Langford pairing from memory before moving on to harder problems.

Reference excerpt

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

See also Stirling permutation, a different type of permutation of the same multiset

Notes

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 (341): 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 John E. Miller, Langford's Problem, 2006. (with an extensive bibliography). Weisstein, Eric W. "Langford's Problem". MathWorld.

Illustrations

Worked examples

Example 1 — a first encounter with Langford pairing

Start with the simplest possible case. Write down what Langford pairing claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Langford pairing before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Langford pairing ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Langford pairing

In research: Langford pairing appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Langford pairing in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Langford pairing is common in secondary-school and first-year university syllabi. It links to neighbouring topics Combinatorics, Permutations, so understanding it makes those chapters shorter.
In everyday life: Look for Langford pairing outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Langford pairing” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Langford pairing in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Langford pairing means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Langford pairing out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Langford pairing in simple terms?

Why does Langford pairing matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Langford pairing?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Langford pairing.