You have a drawer with n shoelaces in it. You reach into the drawer and select two lace ends at random, and tie them together. Repeat this until there are no more untied lace ends left.

If the two ends are from the same lace, or from the same group of laces already tied at their ends, it will form a loop, and therefore no longer have any free ends.

Continue this until all laces are parts of loops, of either 1 lace, 2 laces, etc.

When you're finished, a certain number of loops will have been formed in this fashion, consisting of one or more laces.

What is the expected number of loops?

First note that every time two ends are tied the number of lace ends is reduced by two whether or not a loop is made.

This means for n laces there will be n tieings.  Also, after each tieing there will be two less ends.

With x laces remaining the probability of forming a loop is
1/(2x-1)
and the probability of not forming  a loop is
(2x-2)/(2x-1)

With 1 lace the expected number of loops is 1. 


E(1)=1
E(n) = E(n-1)*(2n-2)/(2n-1) + (E(n-1)+1)*1/(2n-1)

The first few terms are 1, 4/3, 23/15, 176/105, 563/315

I'm still searching for an explicit formula.  The denominators of the fractions are the double factorials of odd numbers, but I don't know the numerators yet.

Posted by Jer on 2005-04-05 19:14:21