%I A078700
%S A078700 1,2,6,30,192,1560,15120,171360,2217600,32296320,522547200,9300614400,
%T A078700 180583603200,3798482688000,86044973414400,2088355965696000,
%U A078700 54064489070592000,1487129136869376000,43312058119249920000
%N A078700 Number of symmetric ways to lace a shoe that has n pairs of eyelets such 
               that each eyelet has at least one direct connection to the opposite 
               side.
%C A078700 The lace must pass through each eyelet exactly one and must begin and 
               end at the extreme pair of eyelets.
%H A078700 <a href="Sindx_La.html#lacings">Index entries for sequences related to 
               shoe lacings</a>
%F A078700 a(n) = (n-1)!*Fibonacci(n+1) = A000142(n-1)*A000045(n+1). - Conjectured 
               by Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 23 2005, proved by 
               Antti Karttunen, Jan 06 2007.
%F A078700 Proof of Jovovic's conjecture (AK): Because of the symmetry
%F A078700 and the beginning and ending conditions, we need to consider only n-1
%F A078700 eyelets on the other side. If considering only the distance from the
%F A078700 starting and ending eyelets (the "level" of each eyelet-pair) through
%F A078700 which the lace is traveling (but ignoring on which side it is), the lace
%F A078700 will induce some permutation of {1..(n-1)} after it has visited half 
               of
%F A078700 the eyelets (and the remaining half of its route is wholly determined 
               by
%F A078700 the symmetry). This gives the factor (n-1)!. Independently of this, the
%F A078700 condition that each eyelet has at least one direct connection to the
%F A078700 opposite side, means that there is a simple bijection with binary
%F A078700 strings of length n with no two consecutive 0's. I.e. we mark 0 when 
               the
%F A078700 lace stays on the same side and 1 when it crosses to the other side.
%F A078700 From the starting eyelet the lace can either cross to the other side
%F A078700 (but not to the top one) or stay on the same side. However, after
%F A078700 visiting half of the eylets, the lace MUST cross to the other side (on
%F A078700 the same level), so this leaves n-1 eyelets where the choice is free,
%F A078700 except that there can be no two consecutive 0's on the route. This gives
%F A078700 the factor Fibonacci(n+1).
%e A078700 a(3) = 6: 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 symmetric lacings 
               are: 124356 154326 153426 142536 145236 135246.
%p A078700 ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,
               card <= 1)}, labelled]: seq(combstruct[count](ZL, size=n), n=0..18); 
               - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 26 2008
%t A078700 Table[Fibonacci[n + 2]*n!, {n, 0, 18}] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 
               Jul 09 2009]
%o A078700 (Scheme:) (define (A078700 n) (* (A000142 (- n 1)) (A000045 (+ n 1))))
%Y A078700 Cf. A078698, A078702, A078676, A005922, A000045, A014417.
%Y A078700 Sequence in context: A111059 A009645 A112385 this_sequence A104561 A127482 
               A118747
%Y A078700 Adjacent sequences: A078697 A078698 A078699 this_sequence A078701 A078702 
               A078703
%K A078700 nonn
%O A078700 1,2
%A A078700 Hugo Pfoertner (hugo(AT)pfoertner.org), Dec 18 2002
%E A078700 Jovovic's conjecture proved and more terms as well as Scheme-code added 
               by Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jan 
               02 2007