|
%I #54 Dec 18 2020 08:35:51
%S 2,2,3,2,4,5,2,4,7,8,2,4,8,13,13,2,4,8,15,24,21,2,4,8,16,29,44,34,2,4,
%T 8,16,31,56,81,55,2,4,8,16,32,61,108,149,89,2,4,8,16,32,63,120,208,
%U 274,144,2,4,8,16,32,64,125,236,401,504,233,2,4,8,16,32,64,127,248,464,773,927,377,2,4,8,16,32,64,128,253
%N Square array read by ascending antidiagonals. A(L, n) is a table of sequences representing the number of valid nodes in level n of a labeled binary tree when the labeling rule forbids 1 of the 2^L states given by the last L digits of the parent label.
%C 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.
%C 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).
%C 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.
%C 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:
%C 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
%C 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
%C 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, ...
%C 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ...
%C 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ...
%C 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ...
%C 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ...
%C Taking the antidiagonals of this table gives the present entry F(n).
%C Comparison with the standard n-anacci sequences:
%C 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
%C 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, ...
%C 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, ...
%C 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, ...
%C 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, ...
%C 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, ...
%C 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
%C 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.
%C This method of construction can be generalized (see link) which shows that the output from simple rule definitions is rich in well-known sequences.
%C From _Petros Hadjicostas_, Jul 26 2019: (Start)
%C 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.
%C 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.
%C We have A(L, m) = 2^m for m = 1,...,L-1, and A(L, L) = 2^L - 1. Also,
%C A(L, m) = A(L, m-1) + A(L, m-2) + ... + A(L, m-L) for m >= L + 1.
%C 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.
%C (End)
%H S. Christensen, <a href="https://arxiv.org/abs/1012.5006">Generalized Fibonacci numbers and Blackwell's renewal theorem</a>, arXiv:1012.5006 [math.PR], 2010.
%H S. Christensen, <a href="https://doi.org/10.1016/j.spl.2012.05.003">Generalized Fibonacci numbers and Blackwell's renewal theorem</a>, Statist. Probab. Lett. 82 (2012), 1665-1668.
%H Ross Drewe, <a href="/A144428/a144428.txt">On a generalization of F(n)</a>.
%H O. Dunkel, <a href="http://www.jstor.org/stable/2298801">Solutions of a probability difference equation</a>, Amer. Math. Monthly, 32 (1925), 354-370.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>.
%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%F From _Petros Hadjicostas_, Jul 26 2019: (Start)
%F Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Then A(L, m) = 2^m for m = 1,...,L-1; A(L, L) = 2^L - 1; and A(L, m) = S(L, m) - S(L, m-L) for m >= L + 1, where
%F S(L, m) = Sum_{j = 0..floor(m/(L+1))} (-1)^j * binomial(m-L*j, m - (L+1)*j) * 2^(m - (L+1)*j). (See the formula by _Richard Choulet_ for array A172119. It can also be found in Dunkel (1925).)
%F G.f. for row L >= 2: -1 + (1 - z^L)/(1 - 2*z + z^(L+1)).
%F (End)
%Y Cf. A172119.
%K nonn,tabl
%O 1,1
%A _Ross Drewe_, Oct 06 2008
%E Name clarified by _Petros Hadjicostas_, Jul 26 2019
%E More terms from _Petros Hadjicostas_, Jul 26 2019
|
