A sum that forbids half the pairings

The pigeonhole principle, as more things than boxes put it, is a count that forces something to exist: thirteen letters in twelve pigeonholes put two letters in one hole. How close a fraction can get and the orbit that must come back used the same count to force good approximations and returning orbits. The same kind of argument also runs the other way. A count can show that something cannot exist — that every attempt must fail, without trying any of them — and this essay follows one such count from a child’s toy to a problem that has outrun every formula.

In 1958 the Scottish mathematician C. Dudley Langford watched his son stacking coloured blocks, two of each colour, and noticed that the blocks had been arranged with one block between the red pair, two between the blue pair and three between the yellow pair. He asked for which numbers of colours such an arrangement exists. The answer turns out to depend only on the remainder of the number of colours when divided by four, and the proof is a single sum.

The puzzle and its first answers #

A Langford pairing of order $n$ arranges two copies of each of $1, 2, \dots, n$ in a row of $2n$ places so that the two copies of $k$ have exactly $k$ numbers between them. For $n = 3$ there is essentially one: 3 1 2 1 3 2. The two 1s have one number between them, the two 2s two, the two 3s three. Its reversal, 2 3 1 2 1 3, is the same arrangement read the other way, and throughout this essay an arrangement and its reversal are counted once. For $n = 4$ there is again exactly one: 4 1 3 1 2 4 3 2.

For $n = 1$ and $n = 2$ there are none, which is easy to see by hand: two 1s with one number between them need three places, and there are only two; with $n = 2$ there are four places and the 2s, needing positions three apart, must sit at the two ends, leaving the 1s side by side. For $n = 5$ and $n = 6$ there are none either, but checking that by hand means trying a great many arrangements and watching each fail. For $n = 7$ there are twenty-six. Something is distinguishing the orders, and it is not the size of the search.

Adding up the positions twice #

Number the places 1 to $2n$. Suppose the first copy of $k$ is at place $a_k$. The second copy is then at $a_k + k + 1$, since there are $k$ places between them. Now add up the positions of all $2n$ entries in two ways.

Counted place by place, the positions are just $1, 2, \dots, 2n$, and their sum is $n(2n+1)$. Counted pair by pair, the two copies of $k$ contribute $a_k + (a_k + k + 1) = 2a_k + k + 1$, and the total over all $k$ is

$$2\sum_k a_k + \sum_{k=1}^n (k+1) = 2\sum_k a_k + \frac{n(n+1)}{2} + n.$$

The two totals are equal, so

$$2\sum_k a_k = n(2n+1) - \frac{n(n+3)}{2} = \frac{n(3n-1)}{2}.$$

The left side is twice a whole number, so it is even. Therefore $n(3n-1)/2$ must be even. Working through the remainders: it is even when $n$ leaves remainder 0 or 3 on division by 4, and odd when the remainder is 1 or 2. So no Langford pairing exists when $n$ is 1, 2, 5, 6, 9, 10, 13, 14, … — half of all orders, ruled out at once.

This is counting two ways used as a weapon. Nothing about the arrangement except where its entries sit enters the argument, and the conclusion is a parity: a single bit of information extracted from an equation, which is enough to make the equation impossible. It is the same move that settles the seven bridges, where the parity of the number of bridges at each landmass decides whether a walk can exist, and the move that, in a far more sophisticated form, shows that no square can be cut into an odd number of equal triangles.

Why the sum gives only one bit #

It is natural to try the same trick again with more information: add up the squares of the positions, or the cubes, in two ways, and hope for a second condition. Place by place, the sum of squares is a known number, $\sum_{p=1}^{2n} p^2$. Pair by pair, the two copies of $k$ contribute $a_k^2 + (a_k + k + 1)^2 = 2a_k^2 + 2(k+1)a_k + (k+1)^2$. The equation that results involves $\sum a_k^2$ and $\sum (k+1) a_k$, two unknown quantities that the arrangement can adjust independently, and no remainder of them is forced in the way $2\sum a_k$ was forced to be even. The first sum worked because its unknown part appeared only as twice something; every higher sum mixes the unknown positions with the known gaps in a way that leaves room.

That is the typical shape of a parity obstruction. A single equation, reduced modulo 2, carries a single bit; if that bit is wrong the object cannot exist, and if it is right the equation says nothing more. Stronger obstructions need stronger structure — a colouring, as in the triangle problem, or an invariant that survives more than reduction modulo 2 — and for Langford pairings no stronger obstruction exists, because Davies’s constructions show that the one bit is the only thing that ever goes wrong.

The search, by contrast, sees everything and summarises nothing. Each placement of a pair is a choice of two cells in the row, and a pairing is a choice of $n$ placements that together cover every cell exactly once: an exact-cover problem, the same kind of search that decides whether a Latin square has an orthogonal mate by covering its cells with disjoint transversals. Exact-cover searches answer the question for one order at a time, at a cost that grows exponentially, and never explain their answers.

The count against the search #

A parity argument only forbids. It does not say that every order it allows actually has a pairing; some other obstruction might rule out more. The only way to find out, for any particular order, is to look.

The search places the two largest numbers first, in every free position, then the next largest in every position still free, and so on, abandoning a branch the moment a pair has nowhere to go. It finds pairings at exactly the orders the parity allows — 3, 4, 7, 8, 11, 12 — and at none of the others. Through order 12 the sum is the whole story. Roy Davies proved in 1959 that it is the whole story at every order: for each $n$ leaving remainder 0 or 3 on division by 4 he gave an explicit construction, a recipe that writes down a Langford pairing directly. So the existence question is completely settled, by a one-line count in one direction and a construction in the other.

How many there are #

The counting question is another matter.

There are 1, 1, 26, 150, 17,792 and 108,144 Langford pairings at orders 3, 4, 7, 8, 11 and 12. The numbers grow roughly fivefold per order, counting the empty orders in between, and no formula for them is known — not even an asymptotic one that has been proved. Every value has been found by search. The counts are known up to order 28 or so, where each new value required enormous distributed computations and clever reformulations of the search as an algebraic sum over signs, and beyond that nothing is known except that the numbers keep growing.

Laid out together, the twenty-six pairings of order 7 show no visible pattern. A few things are forced — the two 7s, which need eight places between them, always straddle the middle of the row — but the rest varies freely, and nothing in the list suggests a rule that would predict how many there are. The contrast with the existence question is complete. Existence is decided by one bit of arithmetic; the count is a number that, so far, can only be produced by listing.

What the search costs #

The search tries 16 placements at order 3 and nearly thirty million at order 11, growing by a factor of about seven per order. At the forbidden orders it does all the work of a real search and finds nothing: orders 5, 6, 9 and 10 together cost it over four million placements, to reach the conclusion the parity argument reaches in one line. That is the general relationship between a counting argument and a search. The search can answer any particular question, given time; the count answers infinitely many at once and costs nothing, but only answers the questions it happens to fit.

Most of that work is spent in dead ends. At order 7 the search makes 13,674 placements to find 52 pairings — 26 and their reversals — about 263 placements for every pairing found. At order 8 it makes 83,859 for 300, about 280 each; at order 11, 29,378,526 for 35,584, about 826 each. The pairings become rarer among the partial arrangements the search explores, because a partial arrangement that has placed the large pairs leaves gaps of awkward sizes, and the smaller pairs, which need gaps of exactly the right width, fail to fit far more often than they succeed. A cleverer search would recognise doomed gaps earlier — a gap of width one can only ever hold a number whose partner is elsewhere, and if every remaining partner position is taken the branch is dead — and practical counts use pruning of this kind. None of it changes the exponential shape of the cost; it only lowers the base.

The growth also shows why the counts stop where they do. A factor of seven per order means that order 28 would take something like $7^{17}$ times as long as order 11 by this method, which is out of the question; the published counts beyond order 20 rely on reformulating the count, using an inclusion–exclusion over signs that turns the listing into a sum computable much faster than the arrangements themselves, and even that grows exponentially.

Skolem’s version, and a different residue #

Langford’s puzzle had a predecessor. In 1957 Thoralf Skolem asked for arrangements in which the two copies of $k$ are $k$ places apart rather than having $k$ numbers between them — so the two 1s are neighbours, which a Langford pairing never allows.

The same sum works with one change: the pair contributes $2a_k + k$ instead of $2a_k + k + 1$, and the condition becomes that $n(3n+1)/2$ is even, which holds when $n$ leaves remainder 0 or 1 on division by 4. Order 4 has both kinds, order 5 only Skolem’s, order 3 only Langford’s. The search again agrees with the count at every order up to 12, and Skolem proved that every allowed order has a sequence. The counts — 6, 10, 504, 2,656 and 455,936 at orders 4, 5, 8, 9 and 12 — are again known only by search.

Skolem was not playing with blocks. He wanted the sequences to build Steiner triple systems: collections of three-element groups drawn from a set of points, such that every pair of points lies in exactly one group — the structure behind a schedule in which every pair meets once. A Skolem sequence of order $n$ gives, by a direct recipe, a triple system on $6n + 1$ points, and the systems so built are cyclic: rotating every point by one step around a circle of $6n + 1$ points maps the system to itself. The parity condition then becomes a condition on which triple systems can be built this way, and the remaining residues are covered by small variations — “hooked” sequences with one empty place, introduced by Edwin O’Keefe in 1961.

Counts that forbid and counts that force #

The pigeonhole principle and the Langford sum are two faces of one technique: compare two ways of counting the same total, and read off a consequence. When the count shows that some box must hold two things, it forces existence; when it shows that a required total has the wrong parity, it forbids. The second use is in some ways the more surprising, because it rules out every arrangement without examining any, and it does so with information — one bit — that has nothing to do with the arrangement’s details.

For Langford’s son the consequence was concrete. With three colours of blocks, or four, or seven or eight, the stack can be built; with five, six, nine or ten it cannot, however long the child tries, and the reason has nothing to do with the colours or the blocks — only with whether a certain number is even. A parent could have told the child in advance which towers to give up on, and could not have said, for the towers that work, how many different ways there are to build them.

It is also limited in a precise way. A parity argument can only ever forbid the orders on one side of a residue condition. If some deeper obstruction ruled out an order the parity allowed, the parity argument would never see it; that it does not happen here is Davies’s construction, not the sum. The same pattern recurs throughout combinatorics. The thirty-six officers are the cautionary case: Euler’s guess that orthogonal Latin squares fail at every order two more than a multiple of four was a residue condition, it was true at six, and it was false at every larger such order. A residue that forbids small cases need not forbid large ones, and only a construction can show that the residue is the whole truth.

What the pictures cannot show #

The figures show orders up to 12. The parity argument and Davies’s construction cover every order, but the counts in the figures are the search’s counts and nothing more; the claim that the counts go on growing is supported by values up to the high twenties computed elsewhere, not by a theorem. The table showing that the search finds pairings at exactly the allowed orders is a check of the construction for small cases, not a proof of it.

There is also nothing in the pictures about structure. The twenty-six pairings of order 7 look patternless, and they may be; but a pattern can hide in a list that looks random, and the absence of a formula for the counts may reflect missing ideas rather than genuine disorder. What the pictures do show is the gap between the two questions — existence decided by a sum, number decided only by enumeration — which is the state of the subject.

Still open: a formula, or even a rate #

No formula for the number of Langford pairings is known, and neither is a proved rate of growth. The values grow faster than any fixed ratio over the range computed, and heuristic arguments predict growth roughly like $n^{2n}$ divided by an exponential, the way counts of permutations grow; nothing of the kind has been proved. The same is true of Skolem sequences. Computing the next value, order 31 for Langford pairings, is beyond current methods, and a better algorithm than inclusion–exclusion over signs would be needed to go much further.

The variants are open in their own ways. Generalisations with three or more copies of each number — three 1s with one number between consecutive copies, three 2s with two, and so on — have existence conditions that are known for some families and not others, and for most of them the counts are known only for the first few orders. The simplest of these questions — whether every order allowed by the corresponding counting argument actually has an arrangement — is settled only in part, and for longer runs of copies the counting arguments forbid some cases while no construction yet reaches the rest.