login
Number of ways to lace a shoe that has n pairs of eyelets.
3

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

%S 1,2,14,322,17314,1573952,210985926,38916737688

%N Number of ways to lace a shoe that has n pairs of eyelets.

%C The lace must pass through each eyelet exactly once, must begin and end at the extreme pair of eyelets and cannot pass in order though three adjacent eyelets that are in a line.

%C The lace is "undirected": reversing the order of eyelets along the path does not count as a different solution.

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

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

%e a(3) = 14: 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 125346 124536 125436 152346 153246 152436 154236.

%Y Cf. A078602 for directed solutions, A078676 for symmetric solutions.

%Y a(n) = ( A078602(n) + A078676(n) ) / 2

%K nonn

%O 1,2

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

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