## Ken's Puzzle of the WeekLacing (Short) Shoes

In how many ways can you lace shoes with 2/3/4 pairs of eyelets?  Label the eyelet pairs from top to bottom:
 A B C D (E F) (G H)

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?

Source: I didn't find the original source (if you find it, let me know.)  Here are some related links: Optimum Shoe Lacing, Ian's Shoelace Site.
Solution
Mail to Ken