Langford Pairing

Permutation Problem

A few days ago, I came across this problem:

Getting Started

In combinatorics, this problem has a name: Langford's problem. A permutation of \( (1, 1, 2, 2, \dots, n, n) \) that satisfies the condition given in the probem is known as a Langford pairing or Langford sequence.

For small \( n, \) say \( n = 4, \) Langford pairings can be obtained easily by trial and error: \( (4, 1, 3, 1, 2, 4, 3, 2). \) What if \( n \) is large? We need an algorithm to find a permutation that solves the problem in that case.

There is another question to consider: Is there a solution for every possible \( n? \) One can easily see that there are no Langford pairings for \( n = 1 \) and \( n = 2, \) i.e., the sequences \( (1, 1) \) and \( (1, 1, 2, 2) \) have no Langford pairings.

We need to understand two things:

1. For what values of \( n \) do Langford pairings exist?
2. For the values of \( n \) for which Langford pairings exist, how do we find the Langford pairings?

A simple Python 3 program I wrote to find Langford pairings for small values of \( n \) offers some clues. Here is the program:

def find_solutions(n, s=None):
    # If called from top-level (s=None), create a list of 2n zero
    # values.  Zeroes represent unoccupied cells.
    if s is None:
        s = [0] * (2 * n)

    # Next number to be placed.
    m = max(s) + 1

    # For each i, try to place m at s[i] and s[i + m + 1].
    for i in range(2 * n - m - 1):

        # If s[i] and s[i + m + 1] are unoccupied, ...
        if s[i] == s[i + m + 1] == 0:

            # first place m at s[i] and s[i + m + 1].
            s[i] = s[i + m + 1] = m

            # If m is the last number to be placed, ...
            if m == n:
                # then a solution has been found; yield it.
                yield s[:]
            else:
                # else try to place the next number.
                yield from find_solutions(n, s)

            # Undo placement of m.
            s[i] = s[i + m + 1] = 0


# Count solutions for 1 <= n <= 12.
for n in range(1, 13):
    count = sum(1 for s in find_solutions(n))
    print('n = {:2} => {:6} solutions'.format(n, count))

It takes a few minutes for this program to run. Here is the output of this program:

$ python3 langford.py
n =  1 =>      0 solutions
n =  2 =>      0 solutions
n =  3 =>      2 solutions
n =  4 =>      2 solutions
n =  5 =>      0 solutions
n =  6 =>      0 solutions
n =  7 =>     52 solutions
n =  8 =>    300 solutions
n =  9 =>      0 solutions
n = 10 =>      0 solutions
n = 11 =>  35584 solutions
n = 12 => 216288 solutions

Note that we always talk about Langford pairings in plural in this post. That's because either a sequence has no Langford pairings or it has two or more Langford pairings. There is never a sequence that has only one Langford pairing. That's because if we find at least one Langford pairing for a sequence, the reverse of that Langford pairing is also a Langford pairing. Therefore, when Langford pairings exist for a sequence, they must at least be two in number. Since they occur in pairs, they are always even in number. This is why we don't have to write "one or more Langford pairings" in this post. We can always write "Langford pairings" instead.

Conjecture

From the output above, we can form a conjecture:

For convenience, let us denote the sequence \( (1, 1, 2, 2, \dots, n, n) \) as \( S_n. \) We will now prove the above conjecture in two parts:

1. We will first show that the condition that either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4} \) must hold is a necessary condition for the sequence \( S_n \) to have Langford pairings.
2. We will then show that the condition that either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4} \) must hold is a sufficient condition for the sequence \( S_n \) to have Langford pairings.

Necessity

Let \( S_n = (1, 1, 2, 2, \dots, n, n) \) be a sequence such that it has Langford pairings. Let us pick an arbitrary Langford pairing \( s \) of \( S_n \) and split this Langford pairing \( s \) into two mutually exclusive subsequences \( s_1 \) and \( s_2 \) such that:

• \( s_1 \) contains all numbers in odd numbered positions and
• \( s_2 \) contains all numbers in even numbered positions.

For example, if we pick \( s = (1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4) \) which is a Langford pairing of \( S_7, \) we split \( s \) into \begin{align*} s_1 & = (1, 1, 5, 2, 4, 5, 6), \\ s_2 & = (7, 2, 6, 3, 7, 3, 4). \end{align*}

We can make a few observations:

1. Both occurrences of an even number do not occur in the same subsequence.
2. There are \( \left\lfloor \frac{n}{2} \right\rfloor \) even numbers in each subsequence.
3. Both occurrences of an odd number occur in the same subsequence.
4. There are \( \left\lceil \frac{n}{2} \right\rceil \) odd numbers in each subsequence.

Do these observations hold good for every Langford pairing of any aribrary \( S_n \) for every positive integer value of \( n? \) Yes, they do. We will now prove them one by one:

1. Let us consider an even number \( k \) from a Langford pairing. If the first occurrence of \( k \) lies at the \( i \)th position in the pairing, then its second occurrence lies at the \( (i + k + 1) \)th position. Since \( k \) is even, \( i \) and \( i + k + 1 \) have different parities, i.e., if \( i \) is odd, then \( i + k + 1 \) is even and vice versa. Therefore, if the first occurrence of \( k \) lies at an odd numbered position, its second occurrence must lie at an even numbered position and vice versa. Thus one occurrence of \( k \) must belong to \( s_1 \) and the other must belong to \( s_2. \) This proves the first observation.

2. The number of even numbers between \( 1 \) and \( n, \) inclusive, is \( \left\lfloor \frac{n}{2} \right\rfloor. \) Each of these even numbers has been split equally between \( s_1 \) and \( s_2. \) This proves the second observation.

3. Now let us consider an odd number \( k \) from a Langford pairing. If the first occurrence of \( k \) lies at the \( i \)th position in the pairing, then its second occurrence lies at the \( (i + k + 1) \)th position. Since \( k \) is odd, \( i \) and \( i + k + 1 \) have the same parity. Therefore, either both occurrences of \( k \) belong to \( s_1 \) or both belong to \( s_2. \) This proves the third observation.

4. Each subsequence, \( s_1 \) or \( s_2 \) has \( n \) numbers because we split a Langford pairing \( s \) with \( 2n \) numbers equally between the two subsequences. We have shown that each subsequence has \( \left\lfloor \frac{n}{2} \right\rfloor \) even numbers. Therefore the number of odd numbers in each subsequence is \( n - \left\lfloor \frac{n}{2} \right\rfloor = \left\lceil \frac{n}{2} \right\rceil. \)

From the third observation, we know that the odd numbers always occur in pairs in each subsequence because both occurrences of an odd number occur together in the same subsequence. Therefore, the number of odd numbers in each subsequence must be even. Since the number of odd numbers in each subsequence is \( \left\lceil \frac{n}{2} \right\rceil \) as proven for the fourth observation, we conclude that \( \left\lceil \frac{n}{2} \right\rceil \) must be even.

Now let us see what must \( n \) be like so that \( \left\lceil \frac{n}{2} \right\rceil \) is even.

Let us express \( n \) as \( 4q + r \) where \( q \) is a nonnegative integer and \( r \in \{0, 1, 2, 3\}. \)

• If \( n = 4q + 0, \) then\( \left\lceil \frac{n}{2} \right\rceil = \left\lceil \frac{4q}{2} \right\rceil = 2q. \)
• If \( n = 4q + 1, \) then\( \left\lceil \frac{n}{2} \right\rceil = \left\lceil \frac{4q + 1}{2} \right\rceil = 2q + 1. \)
• If \( n = 4q + 2, \) then\( \left\lceil \frac{n}{2} \right\rceil = \left\lceil \frac{4q + 2}{2} \right\rceil = 2q + 1. \)
• If \( n = 4q + 3, \) then\( \left\lceil \frac{n}{2} \right\rceil = \left\lceil \frac{4q + 3}{2} \right\rceil = 2q + 2. \)

We see that \( \left\lceil \frac{n}{2} \right\rceil \) is even if and only if either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4} \) holds good.

We have shown that if a sequence \( S_n \) has Langford pairings, then either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4}. \) This proves the necessity of the condition.

Sufficiency

If we can show that we can construct a Langford pairing for \( (1, 1, 2, 2, \dots, n, n ) \) for both cases, i.e., \( n \equiv 0 \pmod{4} \) as well as \( n \equiv 3 \pmod{4}, \) then it would complete the proof.

Notation

Let us define some notation to make it easier to write sequences we will use in the construction of a Langford pairing:

• \( (i \dots j)_{even} \) denotes a sequence of even positive integers from \( i \) to \( j, \) exclusive, arranged in ascending order.

  For example, \( (1 \dots 8)_{even} = (2, 4, 6) \) and \( (1 \dots 2)_{even} = (). \)

• \( (i \dots j)_{odd} \) denotes a sequence of odd positive integers from \( i \) to \( j, \) exclusive, arranged in ascending order.

  For example, \( (1 \dots 8)_{odd} = (3, 5, 7) \) and \( (1 \dots 3)_{odd} = (). \)

• \( s' \) denotes the reverse of the sequence \( s. \)

  For example, for a sequence \( s = (2, 3, 4, 5), \) we have \( s' = (2, 3, 4, 5)' = (5, 4, 3, 2). \)

• \( s \cdot t \) denotes the concatenation of sequences \( s \) and \( t. \)

  For example, for sequences \( s = (1, 2, 3) \) and \( t = (4, 5) , \) we have \( s \cdot t = (1, 2, 3) \cdot (4, 5) = (1, 2, 3, 4, 5). \)

Let \( x = \left\lceil \frac{n}{4} \right\rceil. \) Therefore, \[ x = \begin{cases} \frac{n}{4} & \text{if } n \equiv 0 \pmod{4}, \\ \frac{n + 1}{4} & \text{if } n \equiv 3 \pmod{4}. \end{cases} \] Let us now define the following eight sequences: \begin{align*} a & = (2x - 1), \\ b & = (4x - 2), \\ c & = (4x - 1), \\ d & = (4x), \\ p & = (0 \dots a)_{odd}, \\ q & = (0 \dots a)_{even}, \\ r & = (a \dots b)_{odd}, \\ s & = (a \dots b)_{even}. \end{align*} Now let us construct a Langford pairing for both cases: \( n \equiv 0 \pmod{4} \) and \( n \equiv 3 \pmod{4}. \) We will do this case by case.

Case \( n \equiv 0 \pmod{4} \)

If \( n \equiv 0 \pmod{4}, \) we construct a Langford pairing with the following concatenation: \[ s' \cdot p' \cdot b \cdot p \cdot c \cdot s \cdot d \cdot r' \cdot q' \cdot b \cdot a \cdot q \cdot c \cdot r \cdot a \cdot d. \] Let us do an example with \( n = 12. \)

For \( n = 12, \) we get \( x = \frac{n}{4} = 3. \) Therefore, \begin{alignat*}{2} a & = (2x - 1) && = (5), \\ b & = (4x - 2) && = (10), \\ c & = (4x - 1) && = (11), \\ d & = (4x) && = (12), \\ p & = (0 \dots a)_{odd} && = (1, 3), \\ q & = (0 \dots a)_{even} && = (2, 4), \\ r & = (a \dots b)_{odd} && = (7, 9), \\ s & = (a \dots b)_{even} && = (6, 8). \end{alignat*} After performing the specified concatenation, we get the following Langford pairing: \[ ( 8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 12, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9, 5, 12 ). \] Let us now show that any construction of a sequence as per this specified concatenation always leads to a Langford pairing.

Each sequence \( a, \) \( b, \) \( c, \) and \( d \) has one number each. Each sequence \( p, \) \( q, \) \( r, \) and \( s \) has \( x - 1 \) numbers each.

The two occurrences of \( a \) have \( q, \) \( c, \) and \( r \) in between, i.e., \[ (x - 1) + 1 + (x - 1) = 2x - 1 = a \] numbers in between. Similarly, we can check that the two occurrences of \( b \) have \( b \) numbers in between; likewise for \( c \) and \( d. \)

The two occurrences of \( 1 \) belong to \( p \) and \( p'. \) Between these two occurrences of \( 1, \) we have only one element of \( b. \)

We now show that for each \( k \) in \( p, \) there are \( k \) numbers in between. For any \( k \) in \( p, \) there is the sequence \( (0..k)'_{odd} \cdot b \cdot (0..k)_{odd} \) in between the two occurrences of \( k, \) i.e, there are \( \frac{k - 1}{2} + 1 + \frac{k - 1}{2} = k \) numbers in between. Similarly, we can check that for each \( k \) in \( q, \) there are \( k \) numbers in between.

Finally, we show that for each \( k \) in \( r, \) there are \( k \) numbers in between. For any \( k \) in \( r, \) there is the sequence \( (a..k)'_{odd} \cdot q' \cdot b \cdot a \cdot q \cdot c \cdot (a..k)_{odd} \) in between the two occurrences of \( k. \) Note that \( a \) is odd, so the number of integers in this sequence is \[ \frac{k - a - 2}{2} + (x - 1) + 1 + 1 + (x - 1) + 1 + \frac{k - a - 2}{2}. \] Simplifying the above expression and then substituting \( a = 2x - 1, \) we get \[ k - a - 2 + 2x + 1 = k. \] Similarly, we can check that for each \( k \) in \( s, \) there are \( k \) numbers in between.

Case \( n \equiv 3 \pmod{4} \)

If \( n \equiv 3 \pmod{4}, \) we construct a Langford pairing with the following concatenation: \[ s' \cdot p' \cdot b \cdot p \cdot c \cdot s \cdot a \cdot r' \cdot q' \cdot b \cdot a \cdot q \cdot c \cdot r. \] Note that this concatenation of sequences is almost the same as the concatenation in the previous section with the following two differences:

• The sequence \( d \) is not used here.
• The sequence \( a \) in the end has moved to replace the sequence \( d \) in the middle of the concatenation.

Let us do an example with \( n = 11. \) For \( n = 12, \) we get \( x = \frac{n + 1}{4} = 3. \) Therefore, the sequences \( a, \) \( b, \) \( c, \) \( p, \) \( q, \) \( r, \) and \( s \) are same as those in the last example in the previous section. After performing the specified concatenation, we get the following Langford pairing: \[ ( 8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 5, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9 ). \] We can verify that for every \( k \) in a Langford pairing constructed in this manner, there are \( k \) numbers in between. The verification steps are similar to what we did in the previous section.