This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/FibonacciMeanders

From OeisWiki

Jump to: navigation, search

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: A000071, A110236, A141147, A201631, A201632, A201633, A201634, A202411, A203611.

Contents

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[0]
    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 Fibonacci
meander
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.

Personal tools