Like all combinatoric problems, this one is probably equivalent to another, well-known one, but I haven't managed to find such an equivalent problem (and OEIS didn't help), so I offer this one as being possibly new and possibly interesting.
Problem statement
I have $2N$ socks in a laundry basket, and I am hanging them on the hot pipes to dry. To make life easier later, I want to hang them in pairs. Since it is dark where the pipes are, I adopt the following algorithm:
- Take a sock at random from the basket.
- If it matches one that is already on my arm, hang them both on the pipes: the one in my hand and the matching one taken from my arm.
- If it does not match one that is already on my arm, hang it on my arm with the others.
- Do this $2N$ times.
The question is: How long does my arm have to be?
Clearly, the minimum length is $1$, for instance if the socks come out in the order $AABBCC$. Equally clearly, the maximum length is $N$, for instance if the socks come out as $ABCABC$. But what is the likeliest length? Or the average length? Or what sort of distribution do the required lengths have?
It turns out to be easiest to parameterise the results not by $2N$, the number of socks, but by $2N-1$, which I will call $M$.
The first few results
(Notation: $n!!$ is the semifactorial, the factorial including only odd numbers; thus $7!!=7\times 5\times 3\times 1$).
In each case I provide the frequency for each possible arm length, starting with a length of 1. I use frequencies rather than probabilities because they are easier to type, but you can get the probabilities by dividing by $M!!$.
$$ \begin{array}{c|rrrrr} M \\ \hline 1 & 1 \\ 3 & 1 & 2 \\ 5 & 1 & 8 & 6 \\ 7 & 1 & 30 & 50 & 24 \\ 9 & 1 & 148 & 340 & 336 & 120 \\ \end{array} $$ It would be good to know (for example) if these frequencies tend to some sort of known distribution as $M\to\infty$, just as the binomial coefficients do.
But, as I said at the beginning, this may just be a re-encoding of a known combinatorial problem, carrying a lot of previously worked out results along with it. I thought, for instance, of the lengths of random walks in $N$ dimensions with only one step forward and one step back being allowed in each dimension – but that looked too complicated to give any straightforward direction to follow.
Background: methods
In case it is interesting or helpful, I obtained the results above by means of a two-dimensional generating function, in which the coefficient of $y^n$ identified the arm length needed and the coefficient of $x^n$ identified how many socks had been retrieved at the [first] time that this length was reached. Calling the resulting generating function $A_M(x,y)$, the recurrence I used was:
$$A_M=MxyA_{M-2}+x^2(x-y)\frac\partial{\partial x}A_{M-2}+(1-x^2)xy$$
which is based on sound first principles and matches the results of manual calculation up to $M=5$. Having found a polynomial, I substitute $x=1$ and the numbers in the table above are then the coefficients of the powers of $y$.
But, mathematics being close to comedy, all this elaboration may be an unnecessarily complicated way to get to a result too trivial to be found even in OEIS. Is it?