

A252864


Number of pairs in generation n of the tree T defined in Comments.


1



1, 1, 2, 3, 5, 8, 12, 18, 25, 35, 51, 75, 110, 161, 236, 346, 507, 743, 1089, 1596, 2339, 3428, 5024, 7363, 10791, 15815, 23178, 33969, 49784, 72962, 106931
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Generation g(0) of T is (0,0). Thereafter, successive generations accrue according to the rule that if (j,k) is in T, then (j,k+1) and (k,j+k) are in T. An equivalent tree is generated as follows: start with the tree of polynomials, T*, having g(0) = 0 and rule that if p(x) is in T*, then p(x) + 1 and x*p(x) are in T*; then put x = (1+sqrt(5))/2, the golden ratio, and remove duplicates as they occur. Or, to obtain a third guise for T, in T* replace x^2 by x + 1 in every polynomial (e.g., replace x^3 by 2x+1, etc.), and remove duplicates as they occur.
Every ordered pair of nonnegative integers occurs exactly once in T.


LINKS

Table of n, a(n) for n=0..30.
Christian Ballot, Clark Kimberling, and Peter J. C. Moses, Linear Recurrences Originating From Polynomial Trees, Fibonacci Quart. 55 (2017), no. 5, 1527.


FORMULA

Conjecture: g(n) = g(n1) + g(n3) for n >= 12.
Empirical g.f.: (x1)*(x^2+x+1)*(x^8+2*x^7+2*x^6+2*x^5+x^4+x^3+x^2+1) / (x^3+x1).  Colin Barker, Feb 01 2015


EXAMPLE

Ordered pairs (i,j) are abbreviated as i,j in this list of 7 generations of T:
g(0): 0,0
g(1): 0,1
g(2): 0,2 1,1
g(3): 0,3 1,2 2,2
g(4): 0,4 1,3 2,3 2,4 3,3
g(5): 0,5 1,4 2,5 3,4 3,5 3,6 4,4 4,6
g(6): 0,6 1,5 2,6 3,7 4,5 4,7 4,8 5,5 5,7 5,8 6,9 6,10


MATHEMATICA

t = NestList[DeleteDuplicates[Flatten[Map[{# + {0, 1}, {Last[#], Total[#]}} &, #], 1]] &, {{0, 0}}, 30]; s[0] = t[[1]]; s[n_] := s[n] = Union[t[[n + 1]], s[n  1]];
g[n_] := Complement[s[n], s[n  1]]; g[0] = {{0, 0}};
Column[Table[g[z], {z, 0, 9}]]
Table[Length[g[z]], {z, 0, 10}]


CROSSREFS

Sequence in context: A127884 A105858 A299731 * A039899 A039901 A173564
Adjacent sequences: A252861 A252862 A252863 * A252865 A252866 A252867


KEYWORD

nonn,more,changed


AUTHOR

Clark Kimberling, Jan 31 2015


STATUS

approved



