# Counting Problem: ways to choose n pairs, none matching

#### garysolberg2

##### New member
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
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
Thank you very much. I looked up the formula for DERANGEMENT and was able to go from there.

Gary E. Solberg