Counting Problem: ways to choose n pairs, none matching

[garysolberg2]

Hi, I thought this was an easy problem until I tried to solve it.

Suppose you have n pairs of socks in a bag. The socks are not tied together in their respective pairs. How many ways are there to reach into the bag, randomly pulling out 2 socks at a time, and end up at the end with an empty bag and none of the pairs of socks you pulled out match?

 

[soroban]

Re: Counting Problem

Hello, garysolberg2!

This is a surprisingly complicated problem.

Suppose you have n pairs of socks in a bag.
The socks are not tied together in their respective pairs.
How many ways are there to reach into the bag, randomly pulling out 2 socks at a time,
and end up at the end with an empty bag and none of the pairs of socks you pulled out match?

\(\displaystyle \text{Suppose the pairs are: }\:\{aA, bB, cC, dD, \hdots, nN\}\)

\(\displaystyle \text{Take one sock from each pair: }\{a,b,c,d, \hdots, n\}\text{, and arrange them in a row.}\)
. . \(\displaystyle \text{There are: }\,n!\text{ possible arrangements.}\)

\(\displaystyle \text{Take their mates: }\,\{A,B,C,D, \hdots, N\}\text{ and arrange then in a second row}\)
. . \(\displaystyle \text{so that }{\bf no}\text{ sock is matched with its mate.}\)

\(\displaystyle \text{This is called a "derangement" of }n\text{ objects.}\)
. . \(\displaystyle \text{The formula and its derivation are quite complex.}\)
\(\displaystyle \text{Let's call this number: }\,D(n)\)


\(\displaystyle \text{Therefore, the answer is: }\;n!\cdot D(n)\)

 

[garysolberg2]

Thank you very much. I looked up the formula for DERANGEMENT and was able to go from there.

Gary E. Solberg