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

1, 3, 42, 1080, 51840, 3758400, 382838400, 52733721600, 9400624128000, 2105593491456000, 579255485276160000, 191957359005941760000, 75420399121328701440000, 34668462695110852608000000, 18432051070888873171353600000, 11223248177765618214764544000000, 7759395812038133743242706944000000

Offset

1,2

Comments

The lace must follow a Hamiltonian path through the 2n eyelets. At least one of the neighbors of every eyelet must be on the other side of the shoe.

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

Links

Table of n, a(n) for n=1..17.

B. Polster, What is the best way to lace your shoes?, Nature, 420 (Dec 05 2002), 476.

Index entries for sequences related to shoe lacings

Formula

a(1)=1; for n > 1, a(n) = ((n!)^2/2)*Sum_{k=0..floor(n/2)} binomial(n-k, k)^2/(n-k).

Example

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 the three solutions are 1 2 3 4, 3 1 2 4, 1 3 2 4.
For n=3 the first few solutions are 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, 1 4 3 2 5 6, 3 4 1 2 5 6, 3 4 2 1 5 6, 2 4 3 1 5 6, 3 2 4 1 5 6, 2 3 4 1 5 6, 2 3 5 1 4 6, 3 2 5 1 4 6, 2 5 3 1 4 6, 3 5 2 1 4 6, ...

Maple

A078601 := n->((n!)^2/2)*add(binomial(n-k, k)^2/(n-k), k=0..floor(n/2));

Mathematica

a[n_] := If[n == 1, 1, n!^2/2 Sum[Binomial[n-k, k]^2/(n-k), {k, 0, n/2}]];
a /@ Range[1, 17] (* Jean-François Alcover, Oct 01 2019 *)

Prog

(PARI) a(n)=if(n>1, n!^2*sum(k=0, n\2, binomial(n-k, k)^2/(n-k))/2, 1) \\ Charles R Greathouse IV, Sep 10 2015
(Python)
from sympy import factorial, binomial
a = lambda n:((factorial(n)**2)>>1) * sum((binomial(n-k, k)**2)/(n-k) for k in range(0, (n>>1)+1)) if n > 1 else 1
print([a(n) for n in range(1, 18)]) # Darío Clavijo, Mar 06 2024

Crossrefs

See A078602 and A078629 for other ways of counting lacings.

Cf. A123385.

Sequence in context: A366010 A206820 A157542 * A268621 A218308 A195010

Adjacent sequences: A078598 A078599 A078600 * A078602 A078603 A078604

Keyword

nonn

Author

N. J. A. Sloane, Dec 11 2002

Status

approved