login
A361574
a(n) is the number of Fibonacci meanders of length m*n and central angle 360/m degrees where m = 3.
4
1, 3, 8, 21, 68, 242, 861, 3151, 11874, 45192, 173496, 673042
OFFSET
1,2
COMMENTS
A binary curve C is a pair (m, S) such that
(a) S is a list with values in {L, R} that
(b) starts with an L, and
(c) m > 0 is an integer that divides the length of S.
Given a binary curve C = (m, S), we call m the modulus of the curve and S the steps of C. 'L' stands for a positively oriented arc (left turn) and 'R' for a negatively oriented arc (right turn).
Let SS denote a pair of consecutive steps in C. The direction d of a curve at n starts with d = 0, and for n > 0, d = d + 1 if SS = LL and d = d - 1 if SS = RR; otherwise, d remains unchanged.
A binary curve C = (m, S) is a meander if the values d mod m are assumed with equal frequency. A meander is a closed smooth curve in the plane, possibly self-overlapping (see the plots).
A binary curve 'changes direction' if two consecutive steps are of the same type, i.e., is a pair of steps of the form LL or RR.
A Fibonacci meander is a meander that does not change direction to the left except at the beginning of the curve, where any number of left turns can appear.
LINKS
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Enumeration of Dyck paths with air pockets, arXiv:2202.06893 [cs.DM], 2022-2023.
Peter Luschny, Fibonacci meanders.
Susanne Wienand, Example of a meander, Plot and animation.
EXAMPLE
For n = 4 the Fibonacci meanders with central angle 120 degrees and length 12, written as binary strings (L = 1, R = 0), are:
100000010001, 100010000001, 110000000001, 100000100100, 100100000100, 100010001000,
110000001000, 100100100000, 110001000000, 111000000000, 110100100101, 111001001001,
111100010001, 111110000001, 111010010010, 111100100100, 111110001000, 111111000000,
111111110001, 111111111000, 111111111111.
PROG
(SageMath)
def isFibonacci(S: list[bool]) -> bool:
dir, os = True, S[0]
for s in S:
if s and os:
if not dir:
return False
dir = True
else:
dir = False
os = s
return True
def isMeander(n: int, S: list[bool]) -> bool:
if S[0] != True:
return False
vec = [0] * n
max = len(S) // n
dir, ob = 0, True
for b in S:
if b and ob:
dir += 1
elif not b and not ob:
dir -= 1
dir = dir % n
v = vec[dir] = vec[dir] + 1
if v > max:
return False
ob = b
return True
def FibonacciMeanders(m: int, steps: int) -> int:
size = m * steps
count = 0
for a in range(0, size + 1, m):
S = [i < a for i in range(size)]
for c in Permutations(S):
if c[0] == 0: break
if not isFibonacci(c): continue
if not isMeander(m, c): continue
count += 1
print(count)
return count
def FibonacciMeandersColumn(m: int, size: int) -> list[int]:
return [FibonacciMeanders(m, n) for n in range(1, size + 1)]
print([FibonacciMeandersColumn(3, n) for n in range(1, 7)])
CROSSREFS
Cf. A000071 (m=1), A201631 (m=2), A197657.
Sequence in context: A371891 A192235 A148769 * A353424 A156291 A111136
KEYWORD
nonn,more
AUTHOR
Peter Luschny, Mar 16 2023
STATUS
approved