# Lacings continued

N. J. A. Sloane njas at research.att.com
Wed Dec 11 07:17:45 CET 2002

```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.

```