cp's OEIS Frontend

A361574 a(n) is the number of Fibonacci meanders of length m*n and central angle 360/m degrees where m = 3.

%I A361574 #26 Mar 28 2023 15:21:34
%S A361574 1,3,8,21,68,242,861,3151,11874,45192,173496,673042
%N A361574 a(n) is the number of Fibonacci meanders of length m*n and central angle 360/m degrees where m = 3.
%C A361574 A binary curve C is a pair (m, S) such that
%C A361574    (a) S is a list with values in {L, R} that
%C A361574    (b) starts with an L, and
%C A361574    (c) m > 0 is an integer that divides the length of S.
%C A361574 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).
%C A361574 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.
%C A361574 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).
%C A361574 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.
%C A361574 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.
%H A361574 Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2202.06893">Enumeration of Dyck paths with air pockets</a>, arXiv:2202.06893 [cs.DM], 2022-2023.
%H A361574 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/FibonacciMeanders">Fibonacci meanders</a>.
%H A361574 Susanne Wienand, <a href="https://oeis.org/wiki/User:Susanne_Wienand">Counting meanders by dynamic programming</a>.
%H A361574 Susanne Wienand, Example of a meander, <a href="https://oeis.org/wiki/File:Meander,_m%3D3.png">Plot</a> and <a href="http://oeis.org/wiki/File:Meander_m%3D3.gif">animation</a>.
%e A361574 For n = 4 the Fibonacci meanders with central angle 120 degrees and length 12, written as binary strings (L = 1, R = 0), are:
%e A361574 100000010001, 100010000001, 110000000001, 100000100100, 100100000100, 100010001000,
%e A361574 110000001000, 100100100000, 110001000000, 111000000000, 110100100101, 111001001001,
%e A361574 111100010001, 111110000001, 111010010010, 111100100100, 111110001000, 111111000000,
%e A361574 111111110001, 111111111000, 111111111111.
%o A361574 (SageMath)
%o A361574 def isFibonacci(S: list[bool]) -> bool:
%o A361574     dir, os = True, S[0]
%o A361574     for s in S:
%o A361574         if s and os:
%o A361574             if not dir:
%o A361574                 return False
%o A361574             dir = True
%o A361574         else:
%o A361574             dir = False
%o A361574         os = s
%o A361574     return True
%o A361574 def isMeander(n: int, S: list[bool]) -> bool:
%o A361574     if S[0] != True:
%o A361574         return False
%o A361574     vec = [0] * n
%o A361574     max = len(S) // n
%o A361574     dir, ob = 0, True
%o A361574     for b in S:
%o A361574         if b and ob:
%o A361574             dir += 1
%o A361574         elif not b and not ob:
%o A361574             dir -= 1
%o A361574         dir = dir % n
%o A361574         v = vec[dir] = vec[dir] + 1
%o A361574         if v > max:
%o A361574             return False
%o A361574         ob = b
%o A361574     return True
%o A361574 def FibonacciMeanders(m: int, steps: int) -> int:
%o A361574     size = m * steps
%o A361574     count = 0
%o A361574     for a in range(0, size + 1, m):
%o A361574         S = [i < a for i in range(size)]
%o A361574         for c in Permutations(S):
%o A361574             if c[0] == 0: break
%o A361574             if not isFibonacci(c): continue
%o A361574             if not isMeander(m, c): continue
%o A361574             count += 1
%o A361574         print(count)
%o A361574     return count
%o A361574 def FibonacciMeandersColumn(m: int, size: int) -> list[int]:
%o A361574     return [FibonacciMeanders(m, n) for n in range(1, size + 1)]
%o A361574 print([FibonacciMeandersColumn(3, n) for n in range(1, 7)])
%Y A361574 Cf. A000071 (m=1), A201631 (m=2), A197657.
%K A361574 nonn,more
%O A361574 1,2
%A A361574 _Peter Luschny_, Mar 16 2023