login
Number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies certain conditions.
4

%I #9 Mar 31 2012 10:29:01

%S 1,6,100,4244,311424,34883924,5552752356

%N Number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies certain conditions.

%C The lace must follow a Hamiltonian path through the 2n eyelets and cannot pass in order though three adjacent eyelets that are in a line.

%C The lace is "directed": reversing the order of eyelets along the path counts as a different solution (cf. A078674).

%H N. J. A. Sloane, <a href="/A078629/a078629.txt">FORTRAN program</a>

%H <a href="/index/La#lacings">Index entries for sequences related to shoe lacings</a>

%e Label the eyelets 1, ..., n from front to back on the left and from n+1, ..., 2n from back to front on the right. For n=2 all 6 lacings are allowed: 1 2 3 4, 2 1 3 4, 3 1 2 4, 1 3 2 4, 2 3 1 4, 3 2 1 4.

%e a(3) = 100: the first few lacings are: 4 2 1 3 5 6, 2 4 1 3 5 6, 1 4 2 3 5 6, 2 1 4 3 5 6, 1 2 4 3 5 6, 1 3 4 2 5 6, 3 1 4 2 5 6, 4 1 3 2 5 6, 1 4 3 2 5 6, 3 4 1 2 5 6, 4 3 1 2 5 6, 3 4 2 1 5 6, 2 4 3 1 5 6, ...

%Y See A078601 and A078602 for other ways of counting lacings. Cf. A078674.

%K nonn,more

%O 1,2

%A _N. J. A. Sloane_, Dec 12 2002

%E a(7) from _Hugo Pfoertner_, Jan 22 2005