login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078601 Number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies certain conditions. 3
1, 3, 42, 1080, 51840, 3758400, 382838400, 52733721600, 9400624128000, 2105593491456000, 579255485276160000, 191957359005941760000, 75420399121328701440000, 34668462695110852608000000, 18432051070888873171353600000, 11223248177765618214764544000000, 7759395812038133743242706944000000 (list; graph; refs; listen; history; text; internal format)
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(binomial(n-k, k)^2/(n-k), k=0..floor(n/2)).

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

CROSSREFS

See A078602 and A078629 for other ways of counting lacings.

Sequence in context: A336572 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 23 03:58 EDT 2022. Contains 353959 sequences. (Running on oeis4.)