Counting Problem: ways to choose n pairs, none matching

garysolberg2

New member
Joined
Apr 11, 2008
Messages
2
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

Elite Member
Joined
Jan 28, 2005
Messages
5,588
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

New member
Joined
Apr 11, 2008
Messages
2
Thank you very much. I looked up the formula for DERANGEMENT and was able to go from there.

Gary E. Solberg
 
Top