A361574 - OEIS

%I #26 Mar 28 2023 15:21:34

%S 1,3,8,21,68,242,861,3151,11874,45192,173496,673042

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

%C A binary curve C is a pair (m, S) such that

%C    (a) S is a list with values in {L, R} that

%C    (b) starts with an L, and

%C    (c) m > 0 is an integer that divides the length of S.

%C 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 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 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 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 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 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 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/FibonacciMeanders">Fibonacci meanders</a>.

%H Susanne Wienand, <a href="https://oeis.org/wiki/User:Susanne_Wienand">Counting meanders by dynamic programming</a>.

%H 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 For n = 4 the Fibonacci meanders with central angle 120 degrees and length 12, written as binary strings (L = 1, R = 0), are:

%e 100000010001, 100010000001, 110000000001, 100000100100, 100100000100, 100010001000,

%e 110000001000, 100100100000, 110001000000, 111000000000, 110100100101, 111001001001,

%e 111100010001, 111110000001, 111010010010, 111100100100, 111110001000, 111111000000,

%e 111111110001, 111111111000, 111111111111.

%o (SageMath)

%o def isFibonacci(S: list[bool]) -> bool:

%o     dir, os = True, S[0]

%o     for s in S:

%o         if s and os:

%o             if not dir:

%o                 return False

%o             dir = True

%o         else:

%o             dir = False

%o         os = s

%o     return True

%o def isMeander(n: int, S: list[bool]) -> bool:

%o     if S[0] != True:

%o         return False

%o     vec = [0] * n

%o     max = len(S) // n

%o     dir, ob = 0, True

%o     for b in S:

%o         if b and ob:

%o             dir += 1

%o         elif not b and not ob:

%o             dir -= 1

%o         dir = dir % n

%o         v = vec[dir] = vec[dir] + 1

%o         if v > max:

%o             return False

%o         ob = b

%o     return True

%o def FibonacciMeanders(m: int, steps: int) -> int:

%o     size = m * steps

%o     count = 0

%o     for a in range(0, size + 1, m):

%o         S = [i < a for i in range(size)]

%o         for c in Permutations(S):

%o             if c[0] == 0: break

%o             if not isFibonacci(c): continue

%o             if not isMeander(m, c): continue

%o             count += 1

%o         print(count)

%o     return count

%o def FibonacciMeandersColumn(m: int, size: int) -> list[int]:

%o     return [FibonacciMeanders(m, n) for n in range(1, size + 1)]

%o print([FibonacciMeandersColumn(3, n) for n in range(1, 7)])

%Y Cf. A000071 (m=1), A201631 (m=2), A197657.

%K nonn,more

%O 1,2

%A _Peter Luschny_, Mar 16 2023