%I #42 Aug 06 2022 07:20:34

%S 2,15,112,836,6240,46576,347648,2594880,19368448,144568064,1079070720,

%T 8054293504,60118065152,448727347200,3349346516992,24999862747136,

%U 186601515909120,1392812676284416,10396095346638848,77597512067973120,579195715157229568

%N Define the sequence T(a(0),a(1)) by a(n+2) is the greatest integer such that a(n+2)/a(n+1) < a(n+1)/a(n) for n >= 0. This is T(2,15).

%C From _Alois P. Heinz_, Mar 18 2009: (Start)

%C a(n) is also the number of forests in the 2 X (n+1) grid.

%C a(0)=2, because there are 2 forests in the 2 X 1 grid: 1.2 and 1-2.

%C a(1)=15, because there are 15 forests in the 2 X 2 grid:

%C 1.2 1-2 1.2 1.2 1.2 1-2 1-2 1-2 1.2 1.2 1.2 1.2 1-2 1-2 1-2

%C . . . . . | . . | . . | . . | . . | | | | . | | | . | | . |

%C 4.3 4.3 4.3 4-3 4.3 4.3 4-3 4.3 4-3 4.3 4-3 4-3 4-3 4.3 4-3

%C a(n) = 8a(n-1) - 4a(n-2) for n>=2, because each of the a(n-1) forests can be extended by 8 patterns:

%C .o -o .o -o .o -o .o -o

%C .. .. .. .. .| .| .| .|

%C .o .o -o -o .o .o -o -o

%C where 4a(n-2) of these are not forests, namely the extensions of a(n-2) forests by 4 patterns:

%C .o-o -o-o .o-o -o-o

%C .| | .| | .| | .| |

%C .o-o .o-o -o-o -o-o (End)

%H Alois P. Heinz, <a href="/A022026/b022026.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Desjarlais and R. Molina, <a href="https://web.archive.org/web/20060904233419/http://othello.alma.edu/~molina/papers/pdf%20papers/spantree.pdf">Counting Spanning Trees in Grid Graphs</a>

%H Tomislav Doslic, <a href="http://dx.doi.org/10.1007/s10910-013-0167-2">Planar polycyclic graphs and their Tutte polynomials</a>, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (8,-4).

%F G.f.: (2-x)/(1-8x+4x^2). - David Boyd and _Ralf Stephan_, Apr 15 2004

%F From _Peter Bala_, May 03 2014: (Start)

%F a(n) = sum of the entries in the 2 X 2 matrix A^n where A is the 2 X 2 matrix [4, 4; 3, 4].

%F a(n) = (1 + 7*sqrt(3)/12)*(4 + 2*sqrt(3))^n + (1 - 7*sqrt(3)/12)*(4 - 2*sqrt(3))^n. See Desjarlais and Molina. (End)

%F a(n+1) = ceiling(a(n)^2/a(n-1))-1 for all n > 0. - _M. F. Hasler_, Feb 10 2016

%p a:= n-> (Matrix([[15,2]]). Matrix([[8, 1], [-4, 0]])^n)[1, 2]:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Mar 18 2009

%t CoefficientList[Series[(2-x)/(1-8*x+4*x^2), {x, 0, 20}], x] (* _Vaclav Kotesovec_, May 03 2014 *)

%o (PARI) a(n)=([15,2]*[8,1;-4,0]^n)[2] \\ _M. F. Hasler_, Feb 10 2016

%Y Equals A028859(2n+2)/4.

%Y Cf. A022018 - A022025, A022027 - A022032.

%K nonn,easy

%O 0,1

%A _R. K. Guy_