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) = ₁ 2 + 1 ₂ (Where the smaller, lower numbers are dropped out— i.e. 1 2 ₃ 4 is just 1x2x4 = 8)

E(3) = ₁ 2 3 + 1 ₂ 3 + 1 2 ₃

E(4) = ₁ 2 3 4 + 1 ₂ 3 4 + 1 2 ₃ 4 + 1 2 3 ₄

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!