This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 5
 1, 2, 6, 30, 192, 1560, 15120, 171360, 2217600, 32296320, 522547200, 9300614400, 180583603200, 3798482688000, 86044973414400, 2088355965696000, 54064489070592000, 1487129136869376000, 43312058119249920000 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS The lace must pass through each eyelet exactly one and must begin and end at the extreme pair of eyelets. LINKS FORMULA a(n) = (n-1)!*Fibonacci(n+1) = A000142(n-1)*A000045(n+1). - Conjectured by Vladeta Jovovic, Jan 23 2005, proved by Antti Karttunen, Jan 06 2007. Proof of Jovovic's conjecture (Antti Karttunen, Jan 06 2007): (Start) Because of the symmetry and the beginning and ending conditions, we need to consider only n-1 eyelets on the other side. If considering only the distance from the starting and ending eyelets (the "level" of each eyelet-pair) through which the lace is traveling (but ignoring on which side it is), the lace will induce some permutation of {1..(n-1)} after it has visited half of the eyelets (and the remaining half of its route is wholly determined by the symmetry). This gives the factor (n-1)!. Independently of this, the condition that each eyelet has at least one direct connection to the opposite side, means that there is a simple bijection with binary strings of length n with no two consecutive 0's. I.e. we mark 0 when the lace stays on the same side and 1 when it crosses to the other side. From the starting eyelet the lace can either cross to the other side (but not to the top one) or stay on the same side. However, after visiting half of the eylets, the lace MUST cross to the other side (on the same level), so this leaves n-1 eyelets where the choice is free, except that there can be no two consecutive 0's on the route. This gives the factor Fibonacci(n+1). (End) EXAMPLE 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. MAPLE 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, Mar 26 2008 MATHEMATICA Table[Fibonacci[n + 2]*n!, {n, 0, 18}] (* Zerinvary Lajos, Jul 09 2009 *) PROG (Scheme:) (define (A078700 n) (* (A000142 (- n 1)) (A000045 (+ n 1)))) CROSSREFS Cf. A000045, A005922, A014417, A078676, A078698, A078702. Sequence in context: A246541 A112385 A195154 * A176719 A203000 A104561 Adjacent sequences:  A078697 A078698 A078699 * A078701 A078702 A078703 KEYWORD nonn AUTHOR Hugo Pfoertner, Dec 18 2002 EXTENSIONS Jovovic's conjecture proved and more terms as well as Scheme-code added by Antti Karttunen, Jan 02 2007 STATUS approved

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

Last modified December 11 10:48 EST 2018. Contains 318049 sequences. (Running on oeis4.)