A144428 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.

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, 8, 16, 31, 56, 81, 55, 2, 4, 8, 16, 32, 61, 108, 149, 89, 2, 4, 8, 16, 32, 63, 120, 208, 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

Offset: 1

Author

Ross Drewe, Oct 06 2008

Keywords

• nonn
• tabl

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.

From Petros Hadjicostas, Jul 26 2019: (Start)

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)

Links

• S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, arXiv:1012.5006 [math.PR], 2010.
• S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, Statist. Probab. Lett. 82 (2012), 1665-1668.
• Ross Drewe, On a generalization of F(n).
• O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370.
• Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
• Wikipedia, Fibonacci number.
• L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Crossrefs

Cf. A172119.

Formula

From Petros Hadjicostas, Jul 26 2019: (Start)

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

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).)

G.f. for row L >= 2: -1 + (1 - z^L)/(1 - 2*z + z^(L+1)).

(End)

Extensions

Name clarified by Petros Hadjicostas, Jul 26 2019

More terms from Petros Hadjicostas, Jul 26 2019