login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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

Table of n, a(n) for n=1..86.

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.

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)

CROSSREFS

Cf. A172119.

Sequence in context: A238998 A144369 A033822 * A029638 A305820 A272831

Adjacent sequences:  A144425 A144426 A144427 * A144429 A144430 A144431

KEYWORD

nonn,tabl

AUTHOR

Ross Drewe, Oct 06 2008

EXTENSIONS

Name clarified by Petros Hadjicostas, Jul 26 2019

More terms from Petros Hadjicostas, Jul 26 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 18:48 EDT 2020. Contains 334748 sequences. (Running on oeis4.)