I found the Nature article, which gives a formula but no proof (sequence A078601 below). I get a different answer (A078602)! NJAS %I A078601 %S A078601 1,3,42,1080,51840,3758400,382838400,52733721600,9400624128000,2105593491456000, %T A078601 579255485276160000,191957359005941760000,75420399121328701440000,34668462695110852608000000, %U A078601 18432051070888873171353600000,11223248177765618214764544000000,77593958120381337432427069440000 00 %N A078601 a(1)=1; for n > 1, a(n) = ((n!)^2/2)*Sum(binomial(n-k,k)^2/(n-k),k=0..floor(n/2)). %D A078601 B. Polster, What is the best way to lace your shoes?, Nature, 420 (Dec 05 2002), 476. %C A078601 The number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies ce rtain conditions. %O A078601 1,2 %K A078601 nonn %A A078601 njas, Dec 11 2002 %Y A078601 Cf. A078602. %I A078602 %S A078602 1,2,21 %N A078602 Ways to lace a shoe that has n pairs of eyelets. %C A078602 The lace must pass through each eyelet exactly one, must begin and end at the extreme pair of e yelets, and cannot pass though three consecutive and adjacent eyelets that are in a line. %O A078602 1,2 %e A078602 a(3) = 21: label the eyelets 1,2,3 from front to back on the left side then 4,5,6 from back to front on the right side. The lacings are: 124356 154326 153426 142536 145236 132546 135246 and %e A078602 the following and their mirror images: 125346 124536 125436 152346 153246 152436 154236. %K A078602 nonn,bref,more %A A078602 njas, Dec 11 2002 %Y A078602 Cf. A078601.