cp's OEIS Frontend

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

%I A078601 #24 Mar 25 2024 22:27:21
%S A078601 1,3,42,1080,51840,3758400,382838400,52733721600,9400624128000,
%T A078601 2105593491456000,579255485276160000,191957359005941760000,
%U A078601 75420399121328701440000,34668462695110852608000000,18432051070888873171353600000,11223248177765618214764544000000,7759395812038133743242706944000000
%N A078601 Number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies certain conditions.
%C A078601 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.
%C A078601 The lace is "undirected": reversing the order of eyelets along the path does not count as a different solution.
%H A078601 B. Polster, <a href="http://www.qedcat.com/articles/lacing.pdf">What is the best way to lace your shoes?</a>, Nature, 420 (Dec 05 2002), 476.
%H A078601 <a href="/index/La#lacings">Index entries for sequences related to shoe lacings</a>
%F A078601 a(1)=1; for n > 1, a(n) = ((n!)^2/2)*Sum_{k=0..floor(n/2)} binomial(n-k, k)^2/(n-k).
%e A078601 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.
%e A078601 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, ...
%p A078601 A078601 := n->((n!)^2/2)*add(binomial(n-k,k)^2/(n-k),k=0..floor(n/2));
%t A078601 a[n_] := If[n == 1, 1, n!^2/2 Sum[Binomial[n-k, k]^2/(n-k), {k, 0, n/2}]];
%t A078601 a /@ Range[1, 17] (* _Jean-François Alcover_, Oct 01 2019 *)
%o A078601 (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
%o A078601 (Python)
%o A078601 from sympy import factorial, binomial
%o A078601 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
%o A078601 print([a(n) for n in range(1, 18)]) # _Darío Clavijo_, Mar 06 2024
%Y A078601 See A078602 and A078629 for other ways of counting lacings.
%Y A078601 Cf. A123385.
%K A078601 nonn
%O A078601 1,2
%A A078601 _N. J. A. Sloane_, Dec 11 2002