PDA

View Full Version : Counting Problem: ways to choose n pairs, none matching



garysolberg2
04-11-2008, 11:09 AM
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
04-11-2008, 02:19 PM
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?
\text{Suppose the pairs are: }\:\{aA, bB, cC, dD, \hdots, nN\}

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

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

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


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

garysolberg2
04-12-2008, 09:23 AM
Thank you very much. I looked up the formula for DERANGEMENT and was able to go from there.

Gary E. Solberg