A078698 Number of ways to lace a shoe that has n pairs of eyelets such that each eyelet has at least one direct connection to the opposite side.

1, 2, 20, 396, 14976, 907200, 79315200, 9551001600, 1513528934400, 305106949324800, 76296489615360000, 23175289163980800000, 8404709419090575360000, 3587225703492542791680000, 1779970753996760560435200000, 1016036270188884847558656000000, 661106386935312429191528448000000

Offset: 1

Author

Hugo Pfoertner, Dec 18 2002

Keywords

• nonn

Comments

The lace is "directed": reversing the order of eyelets along the path counts as a different solution. It must begin and end at the extreme pair of eyelets,

Examples

			a(3) = 20: 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 135246 and the following and their mirror images: 125346 124536 125436 152346 153246 152436 154236.
Examples for n=2,3,4 can be found following the FORTRAN program at given link.
		

References

• C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 494.

Links

• A. Khrabrov and K. Kokhas, Points on a line, shoelace and dominoes, arXiv:1505.06309 [math.CO], (23-May-2015).
• Hugo Pfoertner, Fortran program.
• Hugo Pfoertner, Results for n=1..4.
• Hugo Pfoertner, Results for n=5.
• Index entries for sequences related to shoe lacings

Crossrefs

Cf. A078700, A078702, A078602.

Programs

Fortran

c Program provided at Pfoertner link

Mathematica

a[n_] := (n-1)!^2 Sum[Binomial[n-k, k]^2, {k, 0, n/2}];
Array[a, 17] (* Jean-François Alcover, Jul 20 2018 *)

Formula

Conjecture: a(n) = (n-1)!^2*A051286(n). - Vladeta Jovovic, Sep 14 2005 (correct, see the Khrabrov/Kokhas reference, Joerg Arndt, May 26 2015)

Extensions

Terms a(9) and beyond (using A051286) from Joerg Arndt, May 26 2015