Challenging combinatorics question?

I know this is an old question but I have only just given it a go.

There are some combinatorial tools that I used for this and will just lay out in the order they are used:

1. Recurrence

2. Cycle index

3. Inclusion exclusion

First, the problem seems to lend itself to a graph enumeration approach, so we are essentially attempting to count the number of non-isomorphic graphs of 14 vertices (under horizontally adjacent vertex swaps) with each vertex having *exactly 1 edge*.

x …. x

x …. x

x …. x

x …. x

x …. x

x …. x

x …. x

The vertices on each row represent a pair of socks of the same colour. Let’s generalize to n pairs of socks for the following treatment.

Firstly, ignoring sock colour, the number of said graphs on 2n *labelled vertices* representing n pairs of socks is simply the number of ways of placing 2n socks into n unlabeled bins each of size 2:

(2n)!/(2^n*n!)

In other words this is the number of sock pairings if we distinguish between “left” and “right” socks.

Next, it will be important that we count the number of graphs on labelled vertices that have mirror symmetry about the vertical central line, to do this we need the **recurrence** mentioned: If there are s(n) symmetric graphs with 2n vertices then there are s(n-1) symmetric graphs with the lowermost pair joined, or 2(n-1)*s(n-2) ways each of the lowest pair may be joined to another pair in the same row. Also we have s(0)=s(1)=1 so:

s(n) = s(n-1) + 2(n-1)*s(n-2) <----

Now, labelling vertices 1 to n left to right, top to bottom the permutation subgroup of row-pair-swaps is the set of 2^n permutations in cycle notation {(1), (12), (34), …, (n-1 n), (12)(34), (12)(56), …, (n-3 n-2)(n-1 n), … , (12)(34)(56)…(n-1 n)}. This is a subgroup as it is generated by the permutations (12), (34), … ,(n-1 n). Hence the cycle index for a graph of this type with 2n vertices has the **cycle index**

P_G(n; z_1, z_2)

= (1/(2^n))*( C(n,0)z_1^0*z_2^n + C(n,1)z_1^1*z_2^(n-1) + … + C(n,n-1)z_1^(n-1)*z_2^1 +C(n,n)z_1^n*z_2^0 )

There are:

C(n,0) permutation (1), it is the identity and has type z_1^n*z_2^0 since it has n 1-cycles and 0 2-cycles.

C(n,1) permutations (12),(34),…,(n-1 n), all are type z_1^(n-1)*z_2^1 since they each have n-1 1-cycles and 1 2-cycle.

C(n,2) permutations (12)(34),(12)(56),…,(n-3 n-2)(n-1 n), all are type z_1^(n-2)*z_2^2 since they each have n-2 1-cycles and 2 2-cycles.

Etc.

The cycle index can be expressed succinctly as P_G(n; z_1,z_2) = (1/(2^n))*(z_1 + z_2)^n although it's only useful once expanded, as we shall see.

The number of non-isomorphic graphs is given by replacing each cycle index term z_1^i*z_2^(n-i) with the number of graphs that remain unchanged under a permutation of this type. It is not too difficult to see that a permutation that keeps n-i horizontally adjacent pairs fixed and swaps i horizontally adjacent pairs will have:

(2*(n-i))!/(2^(n-i)*(n-i)!) * s(i)

graphs that remain unchanged on labelled vertices. Hence the number of non-isomorphic graphs on n pairs of vertices under horizontally adjacent swaps is given by:

|A| = P_G(n) = (1/(2^n))*sum[i=0,n]( C(n,i) (2*(n-i))!/(2^(n-i)*(n-i)!) * s(i) ) <----

But we want the number of such graphs with no horizontally adjacent vertices joined. So if A_k is the set of non-isomorphic graphs with row k joined then |A_k| = P_G(n-1), |A_k n A_l| = P_G(n-2) and so on.

By inclusion-exclusion the required count for n pairs of socks is

|A| – sum(|A_k|) + sum(|A_k n A_l|) – sum(|A_k n A_l n A_m|) + … +- |A_k n A_l n A_m n …| =

P_G(n) – C(n,1)P_G(n-1) + C(n,2)P_G(n-2) – C(n,3)P_G(n-3) + … + (-1)^n*C(n,n)P_G(0) <----

I calculated

s(0) = 1, s(1) = 1, s(2) = 3, s(3) = 7, s(4) = 25, s(5) = 81, s(6) = 331, s(7) = 1303

and

P_G(0) = 1, P_G(1) = 1, P_G(2) = 2, P_G(3) = 5, P_G(4) = 17 , P_G(5) = 73, P_G(6) = 388, P_G(7) = 2461

And if I’ve not made any mistakes then this gives a final count for 7 pairs of socks:

Sock pairings = 822 <----

Hello M3, total pairs possible with 14 total in number is 14 C 2 = 14 x 13 / 1 x 2 = 91 ways

Out of this only 7 pair is perfectly matched. So non matching chances 91-7 = 84.

Hope I have gone in the right track. If it does not fit well please pass on comments.

There are 1854 ways that this can happen. This computation is known as a derangement, and in your problem, the number is the derangement of 7 items. see:

https://en.wikipedia.org/wiki/Derangement

Your problem is equivalent to the hats problem in the "counting derangements" section. The solution is D(7) (or, !7) = 1854