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

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

Offset: 1

Author

Peter Luschny, Mar 16 2023

Keywords

• nonn
• more

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.

Examples

			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.
		

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, Counting meanders by dynamic programming.
• Susanne Wienand, Example of a meander, Plot and animation.

Crossrefs

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

Programs

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)])