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
Christian Ballot, Clark Kimberling, and Peter J. C. Moses, Linear Recurrences Originating From Polynomial Trees, Fibonacci Quart. 55 (2017), no. 5, 15-27.
FORMULA
Conjecture: |g(n)| = |g(n-1)| + |g(n-3)| for n >= 12.
Empirical g.f.: (x-1)*(x^2+x+1)*(x^8+2*x^7+2*x^6+2*x^5+x^4+x^3+x^2+1) / (x^3+x-1). - 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
KEYWORD
nonn,more
AUTHOR
Clark Kimberling, Jan 31 2015
STATUS
approved