Expected number of swaps in a derangement

We will use the idea of breaking down a permutation into cycles again. For example, the permutation $1 \rightarrow 2, 2 \rightarrow 4, 3 \rightarrow 5, 4 \rightarrow 1, 5 \rightarrow 6, 6 \rightarrow 3$ can be written as $(1 2 4) (3 5 6)$ .

A derangement is simply a permutation whose cycle breakdown contains no cycles of length $1$ .

So, a derangement of length 6 could be broken down into cycles of the following lengths $6$ , $4 + 2$ , $3 + 3$ , or $2+2+2$ . (The above is an example of $3 + 3$ ).

We'll take it as self-evident that the number of swaps needed to get a cycle of length $n$ back to its initial order is $n-1$ . Actually this isn't difficult to prove.

Also, for each $n$ there are $(n-1)!$ possible cycles of length $n$ . This is because we can assume without loss of generality that the cycle starts with $1$ , but then any other ordering of digits gives a valid cycle.

All that remains is to count how many possible cycles there are for each pattern and weight them by the number of swaps required:

Length 6: $5! = 120$ derangements, number of swaps $5$ .

Length 4 + Length 2 : There are ${}^6C_4$ ways of dividing the numbers up into the two cycles. The cycle of length $4$ can have $3!$ possible orderings. So ${}^6C_4 \cdot 3! = 90$ derangements; and number of swaps $(4-1) + (2-1)$

Length 3+ Length 3 : This time the number of ways of partitioning the numbers is $\frac{1}{2}{}^6C_3 = 10$ because $(1 2 4)(356)$ and $(356)(124)$ are the same permutation. Then each partition has $2! \cdot 2!$ cycles for a total of $40$ , and the number of swaps is $(3-1) + (3-1)$

Length 2 + Length 2 + Length 2 : The number of partitions is $\frac{1}{3!}{}^6C_2 \cdot {}^4C_2 = 15$ following similar reasoning as the previous case, but each partition only has one possible ordering here. And the number of swaps required here is $3$ .

Totalling it all up, we get $120 \cdot 5 + 90 \cdot 4 + 40 \cdot 4 + 15 \cdot 3 = 1165$

The total number of cases is $120 + 90 + 40 + 15 = 265$ , so we have an expected value of $1165 \over 265$ , which is $233 \over 53$ , giving a sum of $\boxed{286}$ .

A derangement of cards can be reached via an application of a permutation on the set.

These permutations can occur in different cycle lengths, namely 6, 3 and 3, 4 and 2, and 2 2 2. By cycles, I mean that given a permutation of the cards $(1, 2, 3, 4, 5, 6)$ , a cycle of $n$ size is one that involves $n$ elements. For example, a cycle of size $4$ could be a cycle such that $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, 4\rightarrow 1$ .

If a permutation is of a single cycle size 6, then there are at minimum $5$ swaps required to make the cards back in increasing order, since every swap (Except for the final swap) will only result in only one card going to the desired position.

If a permutation is of two cycles size 3, then there are $2 + 2 = 4$ swaps required to get the desired configuration.

If a permutation is of two cycles size 2 and 4, then 4 swaps are required: 1 for the cycle of 2, and 3 for the cycle of size 4.

Finally, if a permutation is of three cycles all size 2, then 3 swaps are required; one for each cycle.

Now that we know the required number of swaps, we need to find the number of permutations for each.

For the cycle of size 6, there are $(6 - 1)! = 120$ permutations. This can be shown by placing 6 points on a graph, each corresponding to a card, and finding the number of unique cyclic paths which visit each point. We start at any arbitrary point, and then have 5 points to go to next, then 4 points, then 3, then 2, then 1, and then we connect back to the starting point. Thus, there are $5!$ unique paths.

For a permutation with cycles of size 3 and 3, there are $\frac{ {6 \choose 3}}{2}$ ways to choose the triples and then two paths to take for each triple, so there are $2{6\choose3} = 40$ in total.

For the permutation with cycles of size 2 and 4, there are ${6 \choose 4}$ ways to choose the elements in the cycle and $3!$ paths in the cycle of 4, giving us $6{6\choose 4} = 90$

Finally, for a permutation with three cycles of size 2, there are $\frac {{6 \choose 4}{4 \choose 2}}{3!} = 15$ .

Multiplying these numbers by their required number of swaps and dividing by $265$ , we get $\frac {233}{53} \rightarrow 233 + 53 = 286$ .

We can use permuatation groups to solve this problem. Notice that the least number of swaps has to be $\lceil \frac{6}{2} \rceil = 3$ because each swap switches two cards and we know no card is in the position that it is to end up in. The greatest number of swaps is $5$ because we minimize $S$ by swapping at least one card to its final position and the fifth swap would put both cards into its final position. Now we consider three cases:

Case 1: Three swaps. There can only be three swaps if there are three groups of two derangements (ex. 214365 if the original is 123456). There are $\frac{\binom{6}{2}\cdot\binom{4}{2}}{3!} \cdot 1 = 15$ derangements that require three swaps. We divide by $3!$ because we do not care about the order of the group (their position is already determined). We multiply by $1$ because there is $1$ derangement in a set with two cards.

Case 2: Four swaps. There can be four swaps with two groups of three derangements (ex. 312645) or a group of four with a group of two derangement (ex. 214563). There are $\frac{\binom{6}{3}}{2!}\cdot2\cdot2= 40$ for the first subcase. We multiple by $2$ because there are $2$ ways to derange a set with three cards. There are $\binom{6}{4}\cdot6\cdot1 = 90$ for the second subcase. We multiple by $6$ because there are $6$ ways to derange a set with four cards that requires three swaps. So in total, there are $40+90=130$ derangements that require four swaps.

Case 3: Five swaps. We know there are $265$ derangements of six cards and there can only be three, four, or five swaps so the rest of the derangements belong here. There are $265-15-130=120$ derangements that require five swaps.

We find expected value with $\frac{3\cdot15+4\cdot130+5\cdot120}{265}=\frac{233}{53}$ so the answer is $233+53=286$ .

We classify the derangement into these $3$ types according to how they are mixed up.

Type $1$ . $3$ pairs are swapped with each other. This one needs 3 swaps to fix. There are $5C2=10$ ways to choose the groups of $3$ and $2$ ways to rearrange in each group, providing $(10)(2)(2)=40$ ways in all.

Type $2$ . $1$ pair is swapped and a set of $4$ is swapped, without any pair being swapped with each other. This one needs 4 swaps to fix. There are $6C2=15$ ways to choose the ones that would go into the pair and $3!=6$ ways to arrange the ones in the groups of $4$ , providing $(15)(6)=90$ ways in all.

Type $3$ . $2$ triplets are swapped with each other without any pair being swapped with each other. This one needs 4 swaps to fix. There are $(5)(3)=15$ ways to choose the pairings.

Type $4$ . All $6$ are swapped with each other without any set of less than $6$ elements being swapped with each other. This one needs 5 swaps to fix. There are $5!=120$ ways to rearrange the $6$ elements.

Hence the expected value of S is $\frac{(40)(3)+(90)(4)+(15)(4)+(120)(6)}{265}=\frac{1260}{265}=\frac{212}{53}$ . Hence $a=212$ and $b=53$ .

The value of $a+b$ is $\boxed{265}$ .

$3$ is the minimum number of swaps because each swap involves $2$ cards, so if we perform less than $3$ swaps, some cards will remain in the original position. $5$ is the maximum number of swaps. In the worst case, we need $1$ swap to bring card $1$ to the correct position, another swap to bring card $2$ , and one swap each for cards $3,4$ and $5$ . Once $5$ cards are in the correct positions, card $6$ should be automatically in place. Thus the possible number of swaps can be $3,4$ or $5$ .

We first count the derangements involving $3$ swaps. This only happens when we swap $3$ pairs of card, so the number is equivalent to the number of ways to arrange $6$ cards into $3$ pairs. The number of ways is $\frac{\binom{6}{2} \binom{4}{2} \binom{2}{2}}{3!} = 15$

Then we will count the number of derangements involving $5$ swaps. This is equivalent to the number of ways to arrange the numbers from $1$ to $6$ in a cycle. To see why, we'll look at the following example. Let's say we have the cycle $1 \rightarrow 4 \rightarrow 3\rightarrow 2\rightarrow 6\rightarrow 5 \rightarrow 1$ . The corresponding derangement is obtained by moving card $1$ to position $4$ , card $4$ to position $3$ , card $3$ to position $2$ , card $2$ to position $6$ , card $6$ to position $5$ and card $5$ to position $1$ . This is the derangement $534162$ , requiring $5$ swaps to restore the order. The number of such cycles is $\frac{6!}{6}=120$

The number of derangement involving $4$ swaps is thus $265-120-15=130$

The expected value of $S$ is $\frac{15 \times 3 + 130 \times 4 + 120 \times 5}{265}=\frac{233}{53}$

Hence $a+b=233+53 = \fbox{286}$