|
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.
Proof of Jovovic's conjecture (AK): 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).
| 