A022026 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).

2, 15, 112, 836, 6240, 46576, 347648, 2594880, 19368448, 144568064, 1079070720, 8054293504, 60118065152, 448727347200, 3349346516992, 24999862747136, 186601515909120, 1392812676284416, 10396095346638848, 77597512067973120, 579195715157229568

Offset: 0

Author

R. K. Guy

Keywords

• nonn
• easy

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).

Crossrefs

Equals A028859(2n+2)/4.

Cf. A022018 - A022025, A022027 - A022032.

Programs

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 *)

PARI

a(n)=([15,2]*[8,1;-4,0]^n)[2] \\ M. F. Hasler, Feb 10 2016

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