Ken's Puzzle of the Week
Lacing (Short) Shoes

Restrictions:

• Lacing must begin with eyelet A and end with eyelet B.  A and B will be tied across together.
• Each eyelet is used exactly once.
• Laces run straight from one eyelet to another.
• Over/under and top/bottom are not important.  Only eyelet-to-eyelet connections are important.  For example, for 2 pairs, ADCB is equivalent to BCDA, even though the "top" lace would be different between the two in actual practice.
• Each eyelet must have at least one useful connection across the pairs to tighten the shoe.  Thus, for 3 pairs, AECFDB would not be valid because E and D do not contribute to tightening.  AEFCDB would be valid since A crosses to B, C to D&F, and E to F.

Feel free to extend this to more pairs.  However, I've read of mathematicians analyzing this problem for seven pairs of eyelets and finding millions of solutions.  Is there a formula or recursive approach to this?

Kirk summarized his finding this way:

I wrote a quick program that check each N digit number for the following conditions:

first digit 0
last digit 1
for i=2,i<=N-1, the sum of the parity  0 < (i-1)+(i)+(i+1) < 3

This gives the values 1, 20, 396, 14976 ....

Plugging these values into OEIS hits exactly: A078698
http://www.research.att.com/~njas/sequences/A078698

Interesting that with the way I worded the problem, I allow for 2 different lacings with i=2, but the rest of the values are the same as Joseph found below.

Joseph had a very thorough analysis:

Let P be the number of pairs of eyelets, and S be the number of times on each side of the shoe that the lace runs through two eyelets in a row on the same side. (So C, the number of crossings, is 2P - 2S - 1.) This assumes that the lacings begin and end on opposite sides of the shoe, so S is the same number on both sides, and C is odd.)

Also, let's ignore the restriction that the lacings must begin and end at the top. This will make the calculations easier. Since all the eyelets on each side are otherwise equivalent, and it must begin and end somewhere, to get the number of lacings that begin and end at the top, we simply have to divide by P^2.

Define G(P,S) as the number of ways to lace of shoe with P pairs of eyelets on each side so that the lace runs between eyelets on the same side S times on each side of the shoe.

G(P,0) is easiest to calculate: the lace always crosses over. In this case there are P ways to choose the first eyelet, P ways to choose the second eyelet, P-1 ways to choose the third, P-1 ways to choose the fourth, P-2 ways to choose each of the next two, and so on, until there is only 1 way to choose each of the last two eyelets, so there are (P!)^2 ways of lacing the shoe with always crossing over.

Now suppose S=1, calculate G(P,1). On each side of the shoe, first choose two eyelets to be connected. The lace will go directly between these two eyelets on each side, and every other time will cross over. Then we effectively have P-1 pairs of eyelets to connect by always crossing over. So G(P,1) = X(P,1)G(P-1,0) = X(P,1) ((P-1)!)^2, where X(P,1) is the number of ways to choose one pair on each side, and likewise G(P,S) = X(P,S)G(P-S,0) = X(P,S) ((P-S)!)^2.

What is X(P,1)? It's going to be a square, since there are the same number of ways of choosing the pair on each side of the shoe, and those ways on one side are independent of the ways on the other side. On one side, you have P ways of choosing the first element of the pair, and P-1 ways of choosing the second element. We don't divide by two here, because a BC pair is different than a CB pair. Here's where the temporary ignoring of the start-and-end-at-top rules helps: If we insist that we start and end at the top, this calculation gets complicated by the fact that A can only appear at the start of a pair, and B can only appear at the end of one. But it is clear that X(P,1) = (P(P-1))^2. For X(P,S) in general, we still have to choose 2S eyelets on each side of the shoe to be paired, but now, while the order within each pair is important, the order of the pairs is not (they will be shuffled later; at this stage a BC pair and a DE pair is equivalent to a DE pair and a BC pair. So we have P!/(P-2S)! divided by S! on each side, or X(P,S) = [P!/(S!(P-2S)!)]^2.

So G(P,S) = [P!/(S!(P-2S)!)]^2 (P-S)!^2 or G(P,S) = [P!(P-S)!/(S!(P-2S)!)]^2.

Then the total number of lacings for P pairs of eyelets, regardless of the number of crossings, is F(P) = the sum of G(P,S) for S = 0 to floor(P/2). To get the number of lacings where we start and end at the top, divide by P^2, so replace the (P!)^2 in each term with ((P-1)!)^2, so get F(P) = sum(S=0..floor(P/2))  [(P-1)!(P-S)!/(S!(P-2S)!)]^2.

So, F(1) = 1.
F(2) = (1!2!/0!2!)^2 + (1!1!/1!0!)^2 = 1 + 1 = 2.
F(3) = (2!3!/0!3!)^2 + (2!2!/1!1!)^2 = 4 + 16 = 20.
F(4) = (3!4!/0!4!)^2 + (3!3!/1!2!)^2 + (3!2!/2!0!)^2 = 6^2 + 18^2 + 6^2 = 396.
F(5) = (4!5!/0!5!)^2 + (4!4!/1!3!)^2 + (4!3!/2!1!)^2 = 24^2 + 96^2 + 72^2 = 14976.
F(6) = (5!6!/0!6!)^2 + (5!5!/1!4!)^2 + (5!4!/2!2!)^2 + (5!3!/3!0!)^2 = 120^2 + 600^2 + 720^2 + 120^2 = 907200.
F(7) = (6!7!/0!7!)^2 + (6!6!/1!5!)^2 + (6!5!/2!3!)^2 + (6!4!/3!1!)^2 = 720^2 + 4320^2 + 7200^2 + 2880^2 = 79315200.

Indeed, millions of solutions for 7 pairs of eyelets (and almost a million for 6 pairs).

And looking back at the sum, if you pull out the ((P-1)!)^2, the remaining part each each term is (P-S choose S)^2, the sum of which is apparently the "Whitney number of level P of the lattice of the ideals of the fence of order 2 P", sequence A051286.