Sock Colors

Solution

Treat the \(2n\) socks as distinct objects: for each shade \(i\in\{1,\dots,n\}\), there are two socks of shade \(i\). A random pairing of the \(2n\) socks is a perfect matching, and all such pairings are equally likely. The total number of pairings is \[ (2n-1)!!=\frac{(2n)!}{2^n n!}. \] So we only need to count the favorable pairings. Let \(x_i\) be the number of pairs of the form \[ (i,i+1), \] for \(i=1,\dots,n-1\). Since there are only two socks of each shade, each \(x_i\) can only be \[ 0 \quad \text{or} \quad 2. \] It cannot be \(1\), because if one sock of shade \(i\) is paired with a sock of shade \(i+1\), then the remaining sock of shade \(i\) would have to be paired with shade \(i-1\) or \(i+1\), forcing another adjacent mixed pair. In fact, a shade can only be used in one of two ways: - its two socks are paired together as \((i,i)\), or - both its socks are paired with the two socks of a neighboring shade, creating two \((i,i+1)\)-pairs. So a favorable pairing is completely determined by choosing a set of disjoint adjacent color-pairs \[ (i,i+1) \] along the path \[ 1-2-3-\cdots-n. \] That is, we choose a matching on the path graph \(P_n\). For every chosen edge \((i,i+1)\), there are exactly \(2\) ways to pair the two socks of shade \(i\) with the two socks of shade \(i+1\). For every unchosen vertex \(i\), the two socks of shade \(i\) must pair together in exactly \(1\) way. So if the matching has \(k\) edges, it contributes \[ 2^k \] favorable sock-pairings. Hence the number of favorable pairings is \[ a_n=\sum_{M} 2^{|M|}, \] where the sum runs over all matchings \(M\) of the path \(P_n\). Now compute \(a_n\). Look at shade \(1\). Either: - the two socks of shade \(1\) are paired together, leaving any favorable pairing on shades \(2,\dots,n\), giving \(a_{n-1}\), or - shade \(1\) is paired with shade \(2\), which must happen in two crosswise ways, and then shades \(3,\dots,n\) may be paired favorably in \(a_{n-2}\) ways, giving \(2a_{n-2}\). So \[ a_n=a_{n-1}+2a_{n-2}, \] with initial conditions \[ a_0=1,\qquad a_1=1. \] The characteristic equation is \[ r^2=r+2, \] whose roots are \[ r=2,\,-1. \] Thus \[ a_n=\alpha 2^n+\beta(-1)^n. \] Using \(a_0=1\) and \(a_1=1\), \[ \alpha+\beta=1, \qquad 2\alpha-\beta=1. \] Solving gives \[ \alpha=\frac23,\qquad \beta=\frac13. \] Therefore \[ a_n=\frac{2^{n+1}+(-1)^n}{3}. \] So the desired probability is \[ \frac{a_n}{(2n-1)!!} = \frac{\frac{2^{n+1}+(-1)^n}{3}}{\frac{(2n)!}{2^n n!}}. \]