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

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

Offset: 0

Author

Clark Kimberling, Jan 31 2015

Keywords

• nonn
• more

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.

Examples

			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
		

Links

• Christian Ballot, Clark Kimberling, and Peter J. C. Moses, Linear Recurrences Originating From Polynomial Trees, Fibonacci Quart. 55 (2017), no. 5, 15-27.

Programs

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}]

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