This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/FibonacciMeanders
Contents
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, A361574, A361575, A361894, A361681, A201634, A202411, A203611.
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 |
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 | A361574 | A361575 |
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 A361894 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: A361574 are the row sums of the triangle A361681 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 |
101 |
1001 |
10101 |
100101 |
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.
