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,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

Melissa Desjarlais and Robert Molina, Counting Spanning Trees in Grid Graphs, Congressus Numerantium (2000), 177-186.

Tomislav Došlić, Planar polycyclic graphs and their Tutte polynomials, J. Math. Chem. (2013) Vol. 51, Issue 6, pp. 1599-1607.

Sergei Shteiner and Pavel Shteyner, Comparing the numbers of subforests and subgraph-degree-tuples, arXiv:2510.26936 [math.CO], 2025. See pp. 1, 3, 6.

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

Equals A028859(2n+2)/4.

Cf. A022018 - A022025, A022027 - A022032.

Sequence in context: A162773 A140637 A342963 * A026113 A052874 A360432

Adjacent sequences: A022023 A022024 A022025 * A022027 A022028 A022029

Keyword

nonn,easy

Author

R. K. Guy

Status

approved