# Matching Socks in Dark Room

### Problem ### Solution

Let $f(n)$ be the number of pairings of $n$ pairs of socks into acceptable pairs. For $n\le 2$ any pairing is acceptable. Furthermore, $f(1)=1,$ $f(2)=3.$

In general, let's start we a sock of the darkest shade. If we happen to pick a sock of the same shade, we are left with computing $f(n-1).$ Otherwise, there is a pair of socks of the next shade; we can choose any of the two and match the other one with the remaining sock of the darkest shade. This gives a recurrence:

$f(n)=f(n-1)+2f(n-2).$

The characteristic equation of the latter is $x^2-x-2=0,$ with roots $x=2$ and $x=-1.$ The general solution of the recurrence depends on two constants: $f(n)=c_12^n+c_2(-1)^n$ which are found from the initial conditions $f(1)=1,$ $f(2)=3.$ Thus we arrive at

$\displaystyle f(n)=\frac{2^{n+1}+(-1)^n}{3}.$

For $10$ pairs of socks, there are $\displaystyle f(10)=\frac{2048+1}{3}=683$ possible matchings.

To find the sought probability, we have to find the total number of pairings, absent any restrictions.

One sock can be matched with any of $19$ but when that picked, the next sock may match with any of the remaining $17,$ and so on. Thus the total number of pairings is

$19!!=19\cdot 17\cdot 15\cdot\ldots\cdot 5\cdot 3\cdot 1.$

The probability we seek equals $\displaystyle \frac{683}{19!!}\approx 10^{-6}.$

### An aside

$f(n)$ could have been found via generating functions. Let's set

\displaystyle\begin{align}F(x)&=\sum_{n=1}^{\infty}f(n)x^n\\ &=1+3x+\sum_{n=3}^{\infty}f(n-1)+2\sum_{n-3}f(n-2)x^n\\ &=1+3x+x\left(F(x)-x\right)+2x^2F(x), \end{align}

from which

\displaystyle\begin{align}F(x)&=\frac{x+2x^2}{1-x-2x^2}=\frac{x}{3}\left(\frac{4}{1-2x}-\frac{1}{1+x}\right)\\ &=\frac{x}{3}\left(4\sum_{n=0}^{\infty}(2x)^n-\sum_{n=0}^{\infty}(-x)^n\right)\\ &=\frac{x}{3}\sum_{n=0}^{\infty}\left(2^{n+2}-(-1)^n\right)x^n\\ &=\sum_{n=0}^{\infty}\frac{2^{n+2}-(-1)^{n+2}}{3}x^{n+1}\\ &=\sum_{n=1}^{\infty}\frac{2^{n+1}+(-1)^{n}}{3}x^{n}. \end{align}

By definition, $f(n)=[x^n]F(x),$ the coefficient of the series by the term $x^n.$ Thus, as before,

$\displaystyle f(n)=\frac{2^{n+1}+(-1)^n}{3}.$

### Acknowledgment

The problem is #184 from A Mathematical Orchard by M. I. Krusemeyer, G. T. Gilbert, L. C. Larson (MAA, 2012).

### Generating Functions 