Chaitanya's Random Pages

August 28, 2013

Permutations of 1,1,2,2,…,n,n with no two adjacent terms equal

Filed under: mathematics — ckrao @ 9:12 pm

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 1,1,2,2,...,n,n, so that no two consecutive terms are equal? For example, 1,2,3,2,3,1 is permitted but 1,2,2,3,1,3 is not.

This can be solved by the principle of inclusion-exclusion as follows. For i=1,...,n Let P_i be the set of permutations of 1,1,2,2,...,n,n in which that the two copies of i are adjacent. We wish to find the number of permutations in \left( \cup_{i=1}^n P_i \right)^c, as we are interested in permutations not contained in any P_i. The total number of permutations (without restriction of order) is (2n)!/2^n. Using symmetry the cardinality a_n of this set can be enumerated as

\begin{aligned} a_n &= \left| \left( \cup_{i=1}^n P_i \right)^c \right| \\ &= \frac{(2n)!}{2^n} - \sum_{i=1}^n \left|P_i \right| + \sum_{i <j} \left| P_i \cap P_j \right| - \sum_{i < j < k} \left| P_i \cap P_j \cap P_k \right| - \ldots + (-1)^{n} \left| P_1 \cap P_2 \ldots \cap P_n \right|\\ &= \frac{(2n)!}{2^n} - n \left| P_1 \right| + \binom{n}{2} \left| P_1 \cap P_2 \right| - ... + (-1)^{n} \left| P_1 \cap P_2 \ldots \cap P_n \right|.\end{aligned}.

The general term \left| P_1 \cap P_2 \ldots \cap P_k \right| 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 (2n-k)!/2^{n-k} ways, where the division by 2^{n-k} is performed as the last n-k pairs are indistinguishable when permuted. We end up with

\displaystyle a_n = \sum_{k= 0}^n (-1)^{k} \binom{n}{k} \frac{(2n-k)!}{2^{n-k}}.

Evaluating this for n = 4 gives \displaystyle a_4 = 8!/2^4 - 4.7!/2^3 + 6.6!/2^2 - 4.5!/2 + 4! = 1080 - 240 + 24 = 864 (noting that the first two terms always cancel). The Venn diagram below shows the number of permutations of 1,1,2,2,3,3,4,4 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,

\begin{aligned} \left|P_1^c \cap P_2 \cap P_3^c \cap P_4^c \right| &= \left|P_2 \right| - 3 \left|P_1 \cap P_2 \right| + 3 \left|P_1 \cap P_2 \cap P_3 \right| - \left| P_1 \cap P_2 \cap P_3 \cap P_4 \right| \\&= \frac{7!}{2^3} - 3 \frac{6!}{2^2} + 3\frac{5!}{2} - 4! \\ &= 630 - 540 + 180 - 24 \\ &= 246.\end{aligned}

4Venn

All of the numbers shown in the Venn diagram add to 864 + 4\times 246 + 6 \times 84 + 4 \times 36 + 24 = 2520 = 8!/2^4, 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 b_n = a_n / n!. The first terms are 0,1,5,36,329 and we can think of b_n as counting the number of ways we can permute 1,1,2,2,...,n,n so that no two adjacent terms are equal and the first occurrence of i always precedes the first occurrence of i+1 (i = 1,2,..., n-1). 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 b_n is linked to the Bessel polynomial y_n(x) evaluated at x=1 (hence it’s the sum of the coefficients of the polynomials – see OEIS A000806 for more information).

Interestingly the b_ns are linked by the recurrence relation

b_n = (2n-1) b_{n-1} + b_{n-2}, \quad b_0 = 1, b_1 = 0,

which we shall now derive.

To be more concrete we shall link b_4 = 864/4! = 36 to b_3 = 5 and b_2 = 1 (b_4 = 36 = (2(4)-1) \times 5 + 1). 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 n=2 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 n = 3.

We now create an allowable permutation for n=4 in one of three ways:

  1. from each n=2 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) \leftrightarrow (1,2,3,2,3,4,1,4)).
  2. from each n=3 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) \leftrightarrow (1,2,2,3,1,3) \leftrightarrow (1,2,3,1,3,4,2,4)).
  3. from each n = 3 sequence, add 1 to each element, insert 1 at the start of the sequence and a second 1 in any of the remaining (2n-2) = 6 allowable positions – it cannot be placed next to the first 1 (e.g. (1,2,3,1,3,2) \leftrightarrow (1,2,3,1,4,2,4,3)).

Below we see how the n=2 and n=3 generate allowable n=4 sequences.

(1,2,1,2) \leftrightarrow (1,2,3,2,3,4,1,4)

(1,2,1,3,2,3) \leftrightarrow (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) \leftrightarrow (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) \leftrightarrow (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) \leftrightarrow (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) \leftrightarrow (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) \leftrightarrow (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 n=4 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 n=4 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 n=2 sequence.

e.g. (1,2,3,2,3,4,1,4) \rightarrow (2,3,2,3) \rightarrow (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 n =3 sequence. The first occurrence of i will still precede the first occurrence of i+1 in the n=3 sequence.

e.g. (1,2,3,4,1,4,3,2) \rightarrow (2,3,4,4,3,2) \rightarrow (2,3,4,3,2,4) \rightarrow (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 n=3 sequence.

e.g. (1,2,1,3,4,3,4,2) \rightarrow (2,3,4,3,4,2) \rightarrow (1,2,3,2,3,1)

This shows that all allowable n = 4 sequences can be mapped uniquely into one of class 1, 2 or 3, so we have a desired generation of new n = 4 sequences from n=2 and n = 3 through steps 1-3 above. The above can be generalised by replacing 4 with n. Enumerating these now, we have b_{n-2} sequences from case 1, b_{n-1} sequences from case 2 and (2n-2)b_{n-1} sequences from case 3. In total,

\displaystyle b_n = b_{n-2} + b_{n-1} + (2n-2) b_{n-1} = (2n-1) b_{n-1} + b_{n-2},

as we wished to show. The b_0 = 1, b_1 = 0, b_2 = 1 instances are easy to verify and satisfy the above recurrence.

 

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: