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
B. Polster, What is the best way to lace your shoes?, Nature, 420 (Dec 05 2002), 476.
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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 11 2002
STATUS
approved