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?

(In reply to re: Recursive definition by John Reid)

The well-known harmonic numbers H(n) are defined as the sums 1+1/2+1/3+...+1/n.  Thus J(n) defined as 1+1/3+1/5+...+1/(2n-1) can be expressed in terms of harmonic numbers as

J(n) = H(2n)-H(n)/2.

 The harmonic numbers can be expressed as

H(n)=ln(n) + gamma + 1/2n - 1/12n^2 + epsilon(n)/120n^4

where ln is the natural logarithm, 0<epsilon(n)<1, and gamma=0.5772156649... (Euler's constant). Hence

J(n) ~= ln(2sqrt(n)) + gamma/2 + 1/48n^2. 

Thus J(4) = 1+1/3+1/5+1/7 ~= ln(4)+.2886 ~= 1.67 and J(100) ~= ln(20)+.2886 ~= 3.28.  J(n) grows quite slowly with n, and yet the approximate formula is quite accurate even for fairly small n.

Posted by Richard on 2005-04-05 23:41:53