OFFSET
0,1
COMMENTS
From Alois P. Heinz, Mar 18 2009: (Start)
a(n) is also the number of forests in the 2 X (n+1) grid.
a(0)=2, because there are 2 forests in the 2 X 1 grid: 1.2 and 1-2.
a(1)=15, because there are 15 forests in the 2 X 2 grid:
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
. . . . . | . . | . . | . . | . . | | | | . | | | . | | . |
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
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:
.o -o .o -o .o -o .o -o
.. .. .. .. .| .| .| .|
.o .o -o -o .o .o -o -o
where 4a(n-2) of these are not forests, namely the extensions of a(n-2) forests by 4 patterns:
.o-o -o-o .o-o -o-o
.| | .| | .| | .| |
.o-o .o-o -o-o -o-o (End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Desjarlais and R. Molina, Counting Spanning Trees in Grid Graphs
Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.
Index entries for linear recurrences with constant coefficients, signature (8,-4).
FORMULA
G.f.: (2-x)/(1-8x+4x^2). - David Boyd and Ralf Stephan, Apr 15 2004
From Peter Bala, May 03 2014: (Start)
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].
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)
a(n+1) = ceiling(a(n)^2/a(n-1))-1 for all n > 0. - M. F. Hasler, Feb 10 2016
MAPLE
a:= n-> (Matrix([[15, 2]]). Matrix([[8, 1], [-4, 0]])^n)[1, 2]:
seq(a(n), n=0..35); # Alois P. Heinz, Mar 18 2009
MATHEMATICA
CoefficientList[Series[(2-x)/(1-8*x+4*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, May 03 2014 *)
PROG
(PARI) a(n)=([15, 2]*[8, 1; -4, 0]^n)[2] \\ M. F. Hasler, Feb 10 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved