Lacings continued

[Antti Karttunen]

"N. J. A. Sloane" wrote:
> 
> I found the Nature article, which gives a formula but no proof
> (sequence A078601 below). I get a different answer (A078602)!
> NJAS
> 
> %I A078601
> %S A078601 1,3,42,1080,51840,3758400,382838400,52733721600,9400624128000,2105593491456000,
> %T A078601 579255485276160000,191957359005941760000,75420399121328701440000,34668462695110852608000000,
> %U A078601 18432051070888873171353600000,11223248177765618214764544000000,77593958120381337432427069440000
> 00
> %N A078601 a(1)=1; for n > 1, a(n) = ((n!)^2/2)*Sum(binomial(n-k,k)^2/(n-k),k=0..floor(n/2)).
> %D A078601 B. Polster, What is the best way to lace your shoes?, Nature, 420 (Dec 05 2002), 476.
> %C A078601 The number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies ce
> rtain conditions.
> %O A078601 1,2
> %K A078601 nonn
> %A A078601 njas, Dec 11 2002
> %Y A078601 Cf. A078602.
> 
> %I A078602
> %S A078602 1,2,21
> %N A078602 Ways to lace a shoe that has n pairs of eyelets.
> %C A078602 The lace must pass through each eyelet exactly one, must begin and end at the extreme pair of e
> yelets, and cannot pass though three consecutive and adjacent eyelets that are in a line.
> %O A078602 1,2
> %e A078602 a(3) = 21: 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 132546 135246 and
> %e A078602 the following and their mirror images: 125346 124536 125436 152346 153246 152436 154236.
> %K A078602 nonn,bref,more
> %A A078602 njas, Dec 11 2002
> %Y A078602 Cf. A078601.

Dear Neil,

Because you have counted 132546 as a solution in A078602, I reckon that your condition
"and cannot pass though three consecutive and adjacent eyelets that are in a line"
means that "cannot pass _in order_ three consecutive and adjacent eyelets on
the same side."

I think here it is a question of simply counting of permutations with some forbidden
subsequences. I.e. in the case a(3) = 21, we have permutations of [1..6], but
with the first and the last element fixed as 1 and 6, so actually counting the
permutations of [2,3,4,5], but discarding the cases where we would have a
either an increasing [i,i+1,i+2] or decreasing subsequence [i+2,i+1,i]
(where i+2 is either <= n or i > n) e.g. from 4! = 24 permutations of
[1,2,3,4,5,6] with 1 and 6 fixed we have to further discard the three cases
[1,2,3,4,5,6] (violates the condition on both sides), [1,2,3,5,4,6] (on the left side)
and [1,3,2,4,5,6] (on the right side), so we are left with 24-3 = 21 solutions.


Reasoning on these lines should easily (?) lead to a formula for A078602.
At least it's now very easy to write a program in a declarative language
like Prolog or Haskell to count the solutions.


Then regarding Hugo's point about whether the lace enters each hole
(Btw, some of his pictures resemble my son's attempts at this difficult art...)
from the outside or inside, doesn't this just add an extra factor
of 2^(2n) to the count?


Regarding which lace goes underneath or over which other, it seems more
complex. I don't know whether thinking in terms of braids actually clarifies
or confuses this issue:


http://mathworld.wolfram.com/BraidGroup.html
and
http://www.brown.edu/Students/OHJC/topology/index.html
and
http://math.ucr.edu/home/baez/braids.html

(at least one could borrow some notation from there?)


Terveempänä,

Antti Karttunen