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

Powered by vBulletin® Version 4.2.3 Copyright © 2019 vBulletin Solutions, Inc. All rights reserved.