## Follow Up: Loops and the Harmonic Series.

In an earlier post Spaghetti Loops, we asked several problems that we promised had something to do with the number e.

The first question really has to do more with the famous harmonic series; in this post we showed that the sum

1 + 1/2 + 1/3 + 1/4 + …. + 1/n

adds up to about the natural log of n, plus a small constant, Euler’s γ ≈ .577215664901… In other words, to sum up to, say N, at least e(N- γ) terms are used.

What is the connection to spaghetti loops?

It’s a bit easier to think first about a bowl full of extension cords, instead. Just as before, we reach in, pull out a socket, pull out a plug, and insert the plug into the socket. We repeat this until all the plugs and all the sockets are used. The question is: what is the expected number of loops?

The spaghetti problem is harder: when we count arrangements of cords, each individual cord can only be oriented in one direction in a loop. But an individual spaghetti noodle could be turned around or not, as we trace around a loop of noodles.

First let’s count the total number of ways to hook up n extension cords. The plug of cord #1 will be in any of n sockets; the plug of cord #2 will in any of the remaining N-1 sockets, etc. All together there will be n x (n-1) x … x 1 = n! possible arrangements of the cords. So far so good!

Let #(n,m) be the number of ways to hook up n cords so they are in exactly m loops. Some easy observations are that #(n, m<0) = 0, #(n, m>n) = 0 (there are no ways to have no loops, and no ways to have more loops than cords). Can you see that #(n,n) = 1? Incidentally, remember that the total number of arrangements of n cords is n!, so #(n,1)+#(n,2)+ … #(n,n) = n!

Now the key observation is that #(n,m) is related to #(n-1,m) and #(n-1,m-1). Imagine removing the nth cord from an arrangement. If it is a loop all by itself, we will have an arrangement with one less cord, and one less loop, and this can occur (by definition) in #(n-1,m-1) ways. Or if the nth cord is attached into some larger loop, we can remove it, and reattach the loose ends, obtaining an arrangement with n-1 cords and m loops. Any given arrangement of n-1 cords and m loops could have been obtained in n-1 ways in this manner: there are n-1 different spots that the nth cord could have been removed from. So there are #(n-1,m) x (n-1) ways this could have occurred.

Thus #(n,m) = #(n-1,m-1) + (n-1) #(n-1,m)

The real thing we want to know is the expected number of loops with n cords.This will be a weighted average of the number of ways to get each number of loops: Let

E(n) = (1 x #(n,1) + 2 x #(n,2) + 3 x #(n,3) + … + n x #(n,n) )

Then the expected number, choosing at random, is E(n)/n! (remember that n! is the total number of arrangements)

The kicker is that we can use our recursion formula for # to work out a recursion formula for E(n):

E(n) = Σ k #(n,k) = Σ k #(n-1,k-1) + k (n-1) #(n-1,k)

= Σ (k+1) #(n-1,k) + Σ k (n-1) #(n-1,k)

= Σ (k+1 + k(n-1)) #(n-1,k) = Σ (k n + 1) #(n-1,k)

= n Σ k #(n-1,k) + Σ #(n-1,k)

But Σ k #(n-1,k) is the very definition of E(n-1), and we know that Σ #(n-1,k) is the total number of ways of arranging n-1 loops, namely, (n-1)! SO, we have

E(n) = n E(n-1) + (n-1)!

Since E(1) = 1 (think about it), we can work out quickly that E(2) = 3, E(3) = 11, E(4) = 50, …

What on earth is this sequence? Investigating further, we note that E(1) = 1, E(2) = 1 2 + 1 2 (Where the smaller, lower numbers are dropped out— i.e. 1 2 3 4 is just 1x2x4 = 8)

E(3) = 1 2 3 + 1 2 3 + 1 2 3

E(4) = 1 2 3 4 + 1 2 3 4 + 1 2 3 4 + 1 2 3 4

etc.

Now it is not hard to show inductively that this pattern holds for all E(n), and then that

E(n)/n! is just:

1/1 + 1/2 + 1/3 + 1/4 + 1/5 + …. + 1/n

In other words, for large n, the expected number of loops is almost exactly ln n + γ

In order to expect, say, just 10 loops, on average, one needs about e^(10-γ) ≈ 12,000 electrical cords!!

The case for spaghetti is only a little more difficult. If you do the analysis correctly, you should get that the expected number of loops is 1/1 + 1/3 + 1/5 + 1/7 + … + 1/(2n-1) which comes out, asymptotically to

½ ln n + ln 2 + γ/2

WHEW! I’ll tackle the other two problems later. Let me just close with a couple of comments. The extension cord problem is more important that it may seem. We are really asking how many cycles to expect in an arbitrary permutation. This business shows up all over the place. Finally, Peter Winkler poses a fantastic problem that is a direct application of this (I hope that’s not too big a hint) in his wonderful Seven Puzzles You Think You Must Not Have Heard Correctly!

1. ### strauss said,

October 13, 2008 at 9:15 pm

I should have mentioned: with 100 extension cords, one can expect about 5.2 loops on average; with 100 spaghetti noodles, one can expect about 3.3 loops.

Do those numbers seem reasonable? Intuitively (and wrongly) I myself would guess that one would have more loops than that, on average!

2. ### stevestyle said,

October 14, 2008 at 11:50 am

I have an alternative proof for the expected number of loops where we are dealing with extension cords.

Let e(r) be the expected number of loops of length r where r <= n. Each such loop contains r cords. So the expected number of cords which are in a loop of length r is re(r). The probability of a random cord being part of a loop of length r is re(r)/n.

We can calculate this probability a different way. Starting with our random cord:
It will be in a loop of length 1 if it connects to itself, the probability is 1/n.
It will be in a loop of length 2 if it connects to a different cord which then connects to the first, probability (n-1)/n x 1/(n-1) = 1/n.
In general the probability of being in a loop of length r is (n-1)/n x (n-2)/(n-1) x (n-3)/(n-2) x … x (n+1-r)/(n+2-r) x 1/(n+1-r) = 1/n.
So the probability of a random cord being in a loop of length r is always 1/n. Interestingly this doesn’t depend on r (except that r must be less than n).

Before we showed that this probability was re(r)/n, so we have re(r)/n = 1/n and so e(r) = 1/r. The expected number of loops of length r is 1/r. This time the answer doesn’t depend on n (except that r must be less than n).
The expected number of loops is the sum of the expected number of loops of each size which is
e(1) + e(2) +e(3) + … + e(n) = 1 + ½ + 1/3 + … + 1/n

3. ### strauss said,

October 14, 2008 at 12:32 pm

That is very slick. I may go back and edit this post with this simpler argument…

4. ### stevestyle said,

October 14, 2008 at 1:03 pm

Thanks, I wasn’t sure if it was valid to add the expected values. You can avoid this problem by considering the number of cords and loops in all n! possible combinations.

There are n! combinations which contain n! x n cords.
As we have seen the chance of a cord being in a loop of size r is 1/n, so there are n! such cords. Each such loop has r cords and so the number of such loops is n!/r. The total number of loops is the sum of n!/r for 1<=r<=n. Dividing by n! gives the average number of loops per combination which is 1 + ½ + 1/3 + … + 1/n.