This site is supported by donations to The OEIS Foundation.

Fibonacci Meanders

This is a sequel of this blog. We assume the reader familiar with the definitions given there.

KEYWORDS: Fibonacci, Fibonacci meanders, Fibonacci call-trees, Fibonacci forest, classification of Fibonacci meanders.

Concerned with sequences:

Fibonacci meanders

A000071 is the sequence 'Fibonacci numbers − 1' and starts 0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, ... with offset 1. The first two zeros stem from the recursion a(1) = 0, a(2) = 0 and thereafter a(n) = a(n−2) + a(n−1) + 1 and appear in our combinatorial setup as an artifact. Therefore we will look at this sequence shifted two places to the left.

1, 2, 4, 7, 12, 20, 33, 54, 88, ... with offset 1.

This sequence counts the number of Fibonacci meanders. A Fibonacci meander is a meander which does not change direction to the left except at the beginning of the curve where it is allowed to make (or not to make) as many left turns as it likes. Recall that a 'change of direction' of a meander is defined as a pair of steps of the form LL or RR.

More formally, in our setup a meander is of Fibonacci type if it passes the following test:

def isFibonacci(S) :
dir = 1
os = S
for s in S :
if s and os :
dir = dir + 1
if dir == 1 :
return false
else :
dir = 0
os = s
return true

It should be noted that this definition is independent of the meander parameter m.

Definition: A binary curve C = (m, S) is a generalized Fibonacci meander if and only if isMeander(m, S) and isFibonacci(S). (In the case m = 1 we just say C is a Fibonacci meander.)

For instance for m = 3 and length 12 the Fibonacci meanders written as binary strings are given in the table below.

 m len card Fibonaccimeander 3 12 21 100000010001 100010000001 110000000001 100000100100 100100000100 100010001000 110000001000 100100100000 110001000000 111000000000 110100100101 111001001001 111100010001 111110000001 111010010010 111100100100 111110001000 111111000000 111111110001 111111111000 111111111111

The next table counts generalized Fibonacci meanders of length n and central angle 360/m. The rows are indexed by the divisors of n. For example the values in row 12 refer to Fibonacci meanders with central angle 360/m where m = 1, 2, 3, 4, 6 and 12 respectively.

 n \ m 1 2 3 4 5 6 7 Sum 1 1 1 2 2 1 3 3 4 1 5 4 7 3 1 11 5 12 1 13 6 20 6 3 1 30 7 33 1 34 8 54 13 3 71 9 88 8 97 10 143 30 3 177 11 232 233 12 376 70 21 10 3 481 13 609 610 14 986 167 3 1157 15 1596 68 12 1677 16 2583 405 35 3027 17 4180 4181 18 6764 992 242 14 8016 19 10945 10946 20 17710 2450 154 61 20379 21 28656 861 16 29534 OEIS A000071 A201631 A201632 A201633

This table read by rows is A201634.

Classification by binary sum

The columns of the big table above can be seen as the row sums of triangles. These triangles classify the Fibonacci meanders by their binary sum. We will look at the first three cases:

Case m = 1: A000071 are the row sums of the table of Whitney numbers W(n, k) = Sum_{j=0..n} binomial(k, j) read by antidiagonals A004070, and of the triangle A052509, the knights-move Pascal triangle given by

A052509(n, k) = Sum_{j = 0..n} binomial(n - k, k - j) .

1,
1,  1,
1,  2,  1,
1,  3,  2,  1,
1,  4,  4,  2,  1,
1,  5,  7,  4,  2,  1,
1,  6, 11,  8,  4,  2,  1,
1,  7, 16, 15,  8,  4,  2,  1,
1,  8, 22, 26, 16,  8,  4,  2, 1,
1,  9, 29, 42, 31, 16,  8,  4, 2, 1,
1, 10, 37, 64, 57, 32, 16,  8, 4, 2, 1,
1, 11, 46, 93, 99, 63, 32, 16, 8, 4, 2, 1,

The diagonals become stationary at 2n = Sum_{k = 0..n} binomial(n, k).

Case m = 2: A201631 are the row sums of the triangle below.

1,
2,   1,
3,   2,    1,
4,   6,    2,    1,
5,  16,    6,    2,   1,
6,  35,   20,    6,   2,   1,
7,  66,   65,   20,   6,   2,  1,
8, 112,  186,   70,  20,   6,  2,  1,
9, 176,  462,  246,  70,  20,  6,  2, 1,
10, 261, 1016,  812, 252,  70, 20,  6, 2, 1,
11, 370, 2025, 2416, 917, 252, 70, 20, 6, 2, 1,

The second column shows the n-th n-gonal numbers, A060354(n) = n(4 − n(3 − n))/2. The third column is a(n) = n(36 − n(46 − n(29 − n(8 − n))))/12.

The diagonals become stationary at central binomial numbers, binomial(2n, n) = Sum_{k = 0..n} binomial(n, k)^2.

Case m = 3: A201632 are the row sums of the triangle below. The diagonals of this triangle seem to converge to Max Alekseyev's A141147.

1,
2,    1,
5,    2,    1,
10,    8,    2,    1,
17,   40,    8,    2,    1,
26,  161,   44,    8,    2,   1,
37,  506,  263,   44,    8,   2,  1,
50, 1312, 1466,  268,   44,   8,  2, 1,
65, 2948, 6812, 1726,  268,  44,  8, 2, 1,
101,11026,84149,64548,11617,1732,268,44, 8, 2,1,

Challenge 1: Prove that the diagonals of the triangles generated by this classification become stationary and give a general formula depending on m describing the limiting sequences.

 m = 1 A000079 m = 2 A000984 m = 3 A141147 m = 4 ?

Classification by maximal run length

Another way to classify meanders is to classify them by the maximal number of consecutive left turns.  In the binary representation of the meanders this corresponds to the maximal number of consecutive 1s.

Case m = 1: With offsets set properly, n ≥ 0, 0 ≤ k ≤ n:

A104762(n, k) = Sum_{j=0..(n-k)/2} binomial(n-k-j, j).

1,
1,  1,
2,  1,  1,
3,  2,  1, 1,
5,  3,  2, 1, 1,
8,  5,  3, 2, 1, 1,
13,  8,  5, 3, 2, 1, 1,
21, 13,  8, 5, 3, 2, 1, 1,
34, 21, 13, 8, 5, 3, 2, 1, 1,

A000071 are the row sums of this triangle which reduces essentially to the 'one-dimensional' sequence A000045(n-k+1) (an observation of R. J. Mathar).

Case m = 2: The next triangle is not in the database. This triangle is also essentially a single sequence to which two terms are added at each step at the left hand side of the rows.

0,  1,
1,  1,  0,  1,
2,  1,  1,  1,  0,  1,
4,  3,  2,  1,  1,  1,  0,  1,
10,  7,  4,  3,  2,  1,  1,  1,  0, 1,
24, 16, 10,  7,  4,  3,  2,  1,  1, 1, 0, 1,
58, 39, 24, 16, 10,  7,  4,  3,  2, 1, 1, 1, 0, 1,
143, 95, 58, 39, 24, 16, 10,  7,  4, 3, 2, 1, 1, 1, 0, 1,
354,233,143, 95, 58, 39, 24, 16, 10, 7, 4, 3, 2, 1, 1, 1, 0, 1,

The first column seems to be A110236, the number of (1, 0) steps in all peakless Motzkin paths of length n, given by Emeric Deutsch. Deutsch writes: "A110236 can be easily translated into RNA secondary structure terminology". Fortunately Paul Barry gives a simple formula which is accessible without studying genetic engineering:

A110236(n+1) = Sum{k=0..n, C(k+1, n-k+1)*C(k, n-k)};

0, 1, 2, 4, 10, 24, 58, 143, 354, 881, 2204, 5534, 13940, 35213, ...

Analyzing the second column we find the new sequence:

A203611(n) = Sum_{k=0..n} C(k-1, 2*k-1-n)*C(k, 2*k-n);

1, 1, 1, 3, 7, 16, 39, 95, 233, 577, 1436, 3590, 9011, 22691, 57299, ...

Clearly also the sequence which generates the triangle

1, 0, 1, 1, 1, 2, 3, 4, 7, 10, 16, 24, 39, 58, 95, 143, 233, 354, 577, 881, ...

is worth to be included into the database. This sequence zips the first and the second column of the triangle into the rows of the triangle read from the right to the left. A binomial and an hypergeometric formula is given in A202411.

Challenge 2: Give a general formula depending on m which describes the general form of the sequences to which the triangles generated by this classification essentially reduce. These sequences can be seen as generalizations of the Fibonacci numbers.

 m = 1 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... A000045 m = 2 1, 0, 1, 1, 1, 2, 3, 4, 7, 10, 16, 24, ... A202411 m = 3 1, 0, 1, 1, 1, 2, 2, 3, 4, 6, 13, 16, 18, 40, 60, 74, 135, 202, 282, 515, ...

Generating Fibonacci meander

It is fun to observe how the recurrence of the Fibonacci numbers can be translated into an algorithm to generate the Fibonacci meanders. Assume you have already computed the Fibonacci meanders of length n-2 and n-1, F(n-1) and F(n-2). Append to each m in F(n-1) a '0' and append to each m in F(n-2) a '01'; additionally add the 'unity string' 11...1 of length n to the collection.

This construction can be implemented with Sage like this:

def FibonacciMeander(n) :
Fib1 = ["1"]
if n == 1 :  return Fib1
Fib2 = ["10", "11"]
if n == 2 : return Fib2
return GenerateFibonacciMeander(Fib1, Fib2, n - 3)

def GenerateFibonacciMeander(Fib1, Fib2, n) :
Fib3 = []
for s in Fib1 : Fib3.append(s + "01")
for s in Fib2 : Fib3.append(s + "0")
Fib3.append(Fib2[len(Fib2) - 1] + "1")
if n == 0 : return Fib3
return GenerateFibonacciMeander(Fib2, Fib3, n - 1)

def PrintFibonacciMeanderList(k) :
for n in [1..k] :
m = FibonacciMeander(n)
print m, len(m)

PrintFibonacciMeanderList(4)
 1 2 3 4 5 6 1 2 4 7 12 20 1 10 11 101 100 110 111 1001 1101 1010 1000 1100 1110 1111 10101 10001 11001 11101 10010 11010 10100 10000 11000 11100 11110 11111 100101 110101 101001 100001 110001 111001 111101 101010 100010 110010 111010 100100 110100 101000 100000 110000 111000 111100 111110 111111

From the construction we immediately derive that the number of invertible Fibonacci meanders of length n is F(n-1) and the number of non-invertible Fibonacci meanders of length n is F(n-2) + 1.

If the zero sequences of length n are added to these meanders we clearly also have an interpretation of the Fibonacci numbers A000045 as special binary words of length n.

Fibonacci meanders should not be confused with Fibonacci words which are discussed for example in J. Arndt's book Matters Computational (1.27).

The Fibonacci forest

Often the Fibonacci sequence is visualized by a Fibonacci tree. Our setup is different. Note that we plant at each stage a new tree (described in the construction above as "additionally add the 'unity string' 11...1 of length n to the collection"). Thus what we consider here is a Fibonacci forest. The Fibonacci forest is a forest which consists of a disjoint union of rooted trees which are build according to the Fibonacci rules as given above.

Looking at the diagram one can see five concentric circles and five rooted trees, all starting with a green root. Indeed all trees are just copies of the first one rooted in the center. At each stage one more rooted tree is added to the forest and one more circle is added to the diagram. Running around the n-th circle one collects the Fibonacci meanders of length n.

The figure above is the polar-diagram of the Fibonacci forest of level 5. This visualization has the advantage of being more compact for large n than an tree-diagram. A similar idea can be used to visualize large call trees of parallel programs. In its dynamic form this has been called polaranimation and some videos illustrating performance tuning of the parallel Fibonacci algorithm using this technique can be found here.