|
|
COMMENTS
|
A complete labelled binary tree has the root as level 0, 2 nodes at level
1 (each labelled with one of the available symbols 1,2) and 2^n nodes at
level n (each labelled 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 artefact of the construction method, since
a(L,n) is undefined when labels are too short to contain a state
sequence - ie, for all nodes in levels < L.
This method of construction can be generalised (see link) which shows
that the output from simple rule definitions is rich in well-known
sequences.
|
