|
|
COMMENTS
|
A complete labeled binary tree has the root as level 0, 2 nodes at level 1 (each labeled with one of the available symbols 1,2) and 2^n nodes at level n (each labeled with a unique n-digit sequence). The tree can be constructed by adopting a rule that at each successive level, each child node forms its label by adding one symbol to the parent's label.
An incomplete tree can be created by forbidding certain child nodes, using on a state-driven rule. If the state of a node is the last L digits of its label, there are 2^L possible states. Let a(L,n) be the single value denoting the number of valid nodes in level n after applying any given rule and A(L,n) is the sequence of values a(L,2), a(L,3), ..., a(L,n).
Assume this rule: for a given L, all of the 2^L states permit the usual dichotomous branching, except for one state which restricts the output to a single child node. The forbidden child of the pair has a label with the same last digit as the parent state.
This rule creates a set of sequences { A(L,n) } which are essentially the same as the standard "n-step Fibonacci" or "n-anacci" sequences. These can be displayed as the rows of a rectangular array in order of increasing L:
2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, ...
2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ...
2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ...
2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ...
2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ...
Taking the antidiagonals of this table gives the present entry F(n).
Comparison with the standard n-anacci sequences:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, ...
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, ...
0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, ...
0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, ...
0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, ...
0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
shows that the A(L,n) sequences differ only in the absence of the L+2 start-up values. This is an artifact of the construction method, since a(L,n) is undefined when labels are too short to contain a state sequence - i.e., for all nodes in levels < L.
This method of construction can be generalized (see link) which shows that the output from simple rule definitions is rich in well-known sequences.
The author of this array uses F(n) to denote the n-th term of the flattened table (for n >= 1). In addition, it seems that the author uses A(L,n) to denote the term in the L-th row and n-th column of the table. Clearly, L >= 2, but it is not clear whether n starts at 1 or at 2. Thus, in my comments and formulas below I use m to index the columns and start m at 1.
Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Here L is the order of generalized Fibonacci sequence.
We have A(L, m) = 2^m for m = 1,...,L-1, and A(L, L) = 2^L - 1. Also,
A(L, m) = A(L, m-1) + A(L, m-2) + ... + A(L, m-L) for m >= L + 1.
Letting F(n) be the n-th term in the author's sequence (flattened table), we get F((k-1)*(k-2)/2 + i) = A(k-i+1, i) for k >= 2 and i = 1..k-1.
(End)
|
