cp's OEIS Frontend

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

%I A252864 #29 Jan 05 2025 19:51:40
%S A252864 1,1,2,3,5,8,12,18,25,35,51,75,110,161,236,346,507,743,1089,1596,2339,
%T A252864 3428,5024,7363,10791,15815,23178,33969,49784,72962,106931
%N A252864 Number of pairs in generation n of the tree T defined in Comments.
%C A252864 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.
%C A252864 Every ordered pair of nonnegative integers occurs exactly once in T.
%H A252864 Christian Ballot, Clark Kimberling, and Peter J. C. Moses, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf">Linear Recurrences Originating From Polynomial Trees</a>, Fibonacci Quart. 55 (2017), no. 5, 15-27.
%F A252864 Conjecture: |g(n)| = |g(n-1)| + |g(n-3)| for n >= 12.
%F A252864 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
%e A252864 Ordered pairs (i,j) are abbreviated as i,j in this list of 7 generations of T:
%e A252864 g(0):  0,0
%e A252864 g(1):  0,1
%e A252864 g(2):  0,2  1,1
%e A252864 g(3):  0,3  1,2  2,2
%e A252864 g(4):  0,4  1,3  2,3  2,4  3,3
%e A252864 g(5):  0,5  1,4  2,5  3,4  3,5  3,6  4,4  4,6
%e A252864 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
%t A252864 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]];
%t A252864 g[n_] := Complement[s[n], s[n - 1]]; g[0] = {{0, 0}};
%t A252864 Column[Table[g[z], {z, 0, 9}]]
%t A252864 Table[Length[g[z]], {z, 0, 10}]
%K A252864 nonn,more
%O A252864 0,3
%A A252864 _Clark Kimberling_, Jan 31 2015