login
a(n) is the number of terms in expanded form of bivariate polynomial Q_n, where (P_n, Q_n) is defined by: P_0 = x, Q_0 = y, P_(n+1) = P_n + Q_n, Q_(n+1) = P_n * Q_n.
1

%I #102 Sep 13 2023 08:33:56

%S 1,1,2,5,14,40,111,300,797,2098,5499,14389,37634,98435,257516,673827,

%T 1763460,4615686,12082137,31628294

%N a(n) is the number of terms in expanded form of bivariate polynomial Q_n, where (P_n, Q_n) is defined by: P_0 = x, Q_0 = y, P_(n+1) = P_n + Q_n, Q_(n+1) = P_n * Q_n.

%C Programs based on the direct application of the definition quickly reach a limitation by combinatorial explosion, hence this short list of values in section Data. The first conjectured formula (see Formulas) obtained by the observation of a pattern in the 2D shape of Q_n (as drawn in the Examples) is more computationally efficient and makes it possible to produce a significantly longer list of (nonguaranteed) values: see attached a-file in b-file format, section Links.

%C A003686 and A064847 are values of P_n and Q_n at x=y=1 (i.e., sums of coefficients in these polynomials). At x=2, y=1 (or vice versa) P_n and Q_n seem to give same sequences but shifted. At x=y=-1, P_n seems to give A000058 negated interleaved with -1's, while Q_n seems to give A007018 interleaved with the same sequence negated. - _Andrey Zabolotskiy_, May 22 2018

%H Luc Rousseau, <a href="/A296516/a296516_1.txt">201 terms obtained with conjectured formula</a>.

%H Rémy Sigrist, <a href="/A296516/a296516.png">Colored scatterplot of the points (i, j) such that the coefficient of x^i*y^j in Q_14 is nonzero</a> (where the color is function of the coefficient of x^i*y^j in Q_14).

%F Conjectured:

%F a(n) = F(n+1)^2 - T(n-1) - T(F(n-1)) - 2*V(n) - 2*W(n) for n > 0, where

%F F(n) is the n-th Fibonacci number,

%F T(n) is the n-th triangular number,

%F V(n) = Sum_{i=1..n-4} F(i)*(Sum_{j=i+1..n-3} (n-2-j)*F(j)),

%F W(n) = Sum_{i=1..n-3} (n-2-i)*T(F(i)).

%F Or:

%F a(n) = F(n+1)^2 - T(n-1) - T(F(n-1)) - [n>=4]*U(n) where [] is the Iverson bracket, and U(n) = F(n-1)*F(n-3) + F(n+1)*(2*F(n-4)-1) + 5 - 8*(n mod 2).

%F Conjectures from _Colin Barker_, Mar 28 2018: (Start)

%F G.f.: 1 + x*(1 - 5*x + 9*x^2 - 5*x^3 - 2*x^4 + x^5) / ((1 - x)^3*(1 - 3*x + x^2)*(1 - x - x^2)).

%F a(n) = 7*a(n-1) - 18*a(n-2) + 20*a(n-3) - 6*a(n-4) - 6*a(n-5) + 5*a(n-6) - a(n-7) for n > 7.

%F (End)

%F From _Luc Rousseau_, Mar 30 2018: (Start)

%F Derived from the conjectured order-7 linear recurrence above, for n > 0,

%F a(n) = -(1/2)*n^2 + (1/2)*n - 1 + ((2+phi)/10)*(phi^2)^n + ((4-3*phi)/10)*(-phi^(-1))^n + ((1+3*phi)/10)*phi^n + ((3-phi)/10)*(phi^(-2))^n,

%F where phi denotes the golden ratio and lim_{n->oo} a(n+1)/a(n) = phi^2.

%F a(n) = (F(2*n+1) + F(n+2) - n^2 + n - 2) / 2.

%F (End)

%e Q_0 = y -> one term -> a(0) = 1;

%e Q_1 = x*y -> one term -> a(1) = 1;

%e Q_2 = x^2*y + x*y^2 -> two terms -> a(2) = 2;

%e Q_3 = x^3*y + 2*x^2*y^2 + x^3*y^2 + x*y^3 + x^2*y^3 -> five terms -> a(3) = 5;

%e ...

%e Locations of terms in 2D arrays indexed by the exponents of x and y:

%e 0: . 1: .. 2: ... 3: .... 4: ...... 5: .........

%e X .X ..X ...X ....X. .....X...

%e .X. ..XX ...XXX ....XXXX.

%e .XX. ..XXXX ...XXXXXX

%e .XXXX. ..XXXXXXX

%e ..XX.. .XXXXXXXX

%e ..XXXXXX.

%e ..XXXXX..

%e ...XXX...

%t {p[0], q[0]} := {x, y};

%t {p[n_], q[n_]} := {p[n - 1] + q[n - 1], p[n - 1] q[n - 1]};

%t a[n_] := Length@CoefficientRules[q[n]];

%t Table[a[n], {n, 0, 10}] (* _Andrey Zabolotskiy_, _Peter Luschny_, May 30 2018 *)

%t From _Luc Rousseau_, Feb 27 2018: (Start)

%t (* conjectured: *)

%t T[n_] := n*(n + 1)/2

%t F[n_] := Fibonacci[n]

%t V[n_] := Sum[F[k]*(Sum[(n - 2 - l)*F[l], {l, k + 1, n - 3}]), {k, 1, n - 4}]

%t W[n_] := Sum[(n - 2 - l)*T[F[l]], {l, 1, n - 3}]

%t AA[n_] := (F[n + 1])^2 - T[n - 1] - T[F[n - 1]] - 2*V[n] - 2 W[n]

%t Table[AA[n], {n, 1, 50}]

%t (End)

%o (Python)

%o def A296516(n):

%o P, Q = {(1,0)}, {(0,1)}

%o for _ in range(n): P, Q = P|Q, set((p[0]+q[0],p[1]+q[1]) for p in P for q in Q)

%o return len(Q) # _Chai Wah Wu_, Oct 18 2021

%Y Cf. A000045, A000217, A001622, A033192, A003686, A064847, A000058, A007018.

%Y Cf. A005207 (which with +1 added appears to be to P_n as a(n) is to Q_n).

%K nonn,more,nice

%O 0,3

%A _Luc Rousseau_, Feb 27 2018

%E a(15)-a(19) from _Andrey Zabolotskiy_, May 30 2018