A nice question from the Australian Mathematics Competition of 1983 asks how many ways 4 differently coloured pairs of socks can be lined up so that no socks of the same pair are adjacent. More generally, in how many ways can we permute the numbers , so that no two consecutive terms are equal? For example, is permitted but is not.
This can be solved by the principle of inclusion-exclusion as follows. For Let be the set of permutations of in which that the two copies of are adjacent. We wish to find the number of permutations in , as we are interested in permutations not contained in any . The total number of permutations (without restriction of order) is . Using symmetry the cardinality of this set can be enumerated as
The general term can be found by permuting the k + 2(n-k) objects 1-1, 2-2, …, k-k, k+1, k+1, k+2, k+2, …, n, n, where the adjacent terms 1-1 up to k-k are treated as one compound object. This can be done in ways, where the division by is performed as the last pairs are indistinguishable when permuted. We end up with
Evaluating this for gives (noting that the first two terms always cancel). The Venn diagram below shows the number of permutations of that contain each consecutive pair of 11, 22, 33, 44. For example, there are 246 permutations containing the two 2s adjacent, but the two 1s, two 3s and two 4s are not adjacent. All the numbers shown are found again by inclusion-exclusion. For example,
All of the numbers shown in the Venn diagram add to , the total number of permutations of 1,1,2,2,3,3,4,4.
Note that our answer of 864 to the original question is divisible by 4! – this makes sense since we can permute the numbers 1,2,3,4 in any of 24 ways to arrive at another way of arriving at a sequence with the same property that no adjacent terms are equal. With this in mind, let us turn our attention to the sequence . The first terms are 0,1,5,36,329 and we can think of as counting the number of ways we can permute so that no two adjacent terms are equal and the first occurrence of always precedes the first occurrence of (). Call such a sequence allowable. For example 1,2,3,2,3,1 is allowable but 2,3,1,3,1,2 is not. It turns out that the sequence is linked to the Bessel polynomial evaluated at (hence it’s the sum of the coefficients of the polynomials – see OEIS A000806 for more information).
Interestingly the s are linked by the recurrence relation
which we shall now derive.
To be more concrete we shall link to and (). The general case follows similarly.
We can list the allowed permutations of 1,1,2,2 and 1,1,2,2,3,3 as
- (1,2,1,2) for and
- (1,2,1,3,2,3), (1,2,3,1,2,3), (1,2,3,2,1,3), (1,2,3,2,3,1), (1,2,3,1,3,2) for .
We now create an allowable permutation for in one of three ways:
- from each sequence, add 1 to each element, insert 1 at the start of the sequence and 4,1,4 at the end (e.g. (1,2,1,2) (1,2,3,2,3,4,1,4)).
- from each sequence, firstly move the final element next to its other occurrence in the sequence, then add 1 to each element, insert a 1 at the start of the sequence and finally insert a 1 between the two duplicated elements to prevent them from appearing twice in a row (e.g. (1,2,3,1,3,2) (1,2,2,3,1,3) (1,2,3,1,3,4,2,4)).
- from each sequence, add 1 to each element, insert 1 at the start of the sequence and a second 1 in any of the remaining allowable positions – it cannot be placed next to the first 1 (e.g. (1,2,3,1,3,2) (1,2,3,1,4,2,4,3)).
Below we see how the and generate allowable sequences.
(1,2,1,3,2,3) (1,2,3,2,4,1,4,3), (1,2,1,3,2,4,3,4), (1,2,3,1,2,4,3,4), (1,2,3,2,1,4,3,4), (1,2,3,2,4,1,3,4), (1,2,3,2,4,3,1,4), (1,2,3,2,4,3,4,1)
(1,2,3,1,2,3) (1,2,3,4,1,4,2,3), (1,2,1,3,4,2,3,4), (1,2,3,1,4,2,3,4), (1,2,3,4,1,2,3,4), (1,2,3,4,2,1,3,4), (1,2,3,4,2,3,1,4), (1,2,3,4,2,3,4,1)
(1,2,3,2,1,3) (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,2,4), (1,2,3,1,4,3,2,4), (1,2,3,4,1,3,2,4), (1,2,3,4,3,1,2,4), (1,2,3,4,3,2,1,4), (1,2,3,4,3,2,4,1)
(1,2,3,2,3,1) (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,2,3,1) (1,2,1,2,3,4,3,4), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,1,3,2) (1,2,3,1,3,4,2,4), (1,2,1,3,4,2,4,3), (1,2,3,1,4,2,4,3), (1,2,3,4,1,2,4,3), (1,2,3,4,2,1,4,3), (1,2,3,4,2,4,1,3), (1,2,3,4,2,4,3,1)
Let us now see why all allowable sequences have indeed been generated and that no allowable sequence has been repeated (justifying the use of double arrows above).
If we take an allowable sequence, either it ends with 4,1,4 or it does not – if it does it begins to class 1 above. Deleting the 1 at the start and 4,1,4 at the end, then subtracting 1 from each element will map it to an allowable sequence.
e.g. (1,2,3,2,3,4,1,4) (2,3,2,3) (1,2,1,2)
If it does not end in 4,1,4, the second 1 either is between two repeated elements (class 2) or it is not (class 3). The two repeated elements cannot appear at the end since such a sequence could only end with 4,1,4 and we are back to class 1. (If say a 3,1,3 were at the end, the first 4 could only appear after the first 3 and so has not occurred earlier in the sequence.) Deleting the two 1s, moving the second of the repeated elements to the end (we have just seen it is not already at the end so it will become separated from its partner) and then subtracting 1 from each element maps it to an allowable sequence. The first occurrence of will still precede the first occurrence of in the sequence.
e.g. (1,2,3,4,1,4,3,2) (2,3,4,4,3,2) (2,3,4,3,2,4) (1,2,3,2,1,3)
In class 3, since the second 1 is not between two repeated elements, deleting it and the first 1, then subtracting 1 from each element would lead to an allowable sequence.
e.g. (1,2,1,3,4,3,4,2) (2,3,4,3,4,2) (1,2,3,2,3,1)
This shows that all allowable sequences can be mapped uniquely into one of class 1, 2 or 3, so we have a desired generation of new sequences from and through steps 1-3 above. The above can be generalised by replacing 4 with . Enumerating these now, we have sequences from case 1, sequences from case 2 and sequences from case 3. In total,
as we wished to show. The instances are easy to verify and satisfy the above recurrence.