A138977 Number of 2 X n matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1.

3, 19, 121, 771, 4913, 31307, 199497, 1271251, 8100769, 51620379, 328939577, 2096095523, 13356910353, 85113990379, 542370291241, 3456136077171, 22023471375233, 140339755317947, 894284401724697, 5698631790801091, 36313284928708849, 231398467337757579

Offset: 1

Author

Wayne VanWeerthuizen, Apr 05 2008

Keywords

• nonn
• easy

Comments

Horizontally or vertically adjacent entries can differ by at most 1. Diagonally adjacent entries thus differ by at most 2.

Examples

			a(1) = 3:
|1|1|1|
|0|1|2|
a(2) = 19:
|10|11|12| |10|11|12| |10|11|12|
|0*|0*|01| |1*|1*|1*| |21|2*|2*|
(3) (2)(1) (2) (3)(2) (1) (2)(3), total 19.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Michael Han, Sycamore Herlihy, Kirsti Kuenzel, Daniel Martin, and Rachel Schmidt, The number of independent sets in bipartite graphs and benzenoids, arXiv:2311.15334 [math.CO], 2023. See p. 13.
• Index entries for linear recurrences with constant coefficients, signature (7,-4).

Crossrefs

Cf. A138978, A138979.

Programs

Maple

a:= LREtools[REtoproc](a(n+3)=7*a(n+2)-4*a(n+1),a(n),{a(0)=0,a(1)=3,a(2)=19}):
seq(a(n),n=1..100); # Robert Israel, Sep 02 2014

Mathematica

LinearRecurrence[{7, -4}, {3, 19}, 22] (* Jean-François Alcover, Apr 30 2019 *)

PARI

Vec(x*(3 - 2*x) / (1 - 7*x + 4*x^2) + O(x^30)) \\ Colin Barker, Jan 31 2018

Formula

a(n)=b(n)+c(n), where b(1)=2, c(1)=1, b(n+1)=4*b(n)+4*c(n), c(n+1)=2*b(n)+3*c(n).

G.f.: x*(3 - 2*x) / (1 - 7*x + 4*x^2). - N. J. A. Sloane, Apr 06 2008

a(n+2) = 7*a(n+1) - 4*a(n) for n >= 2. - Robert Israel, Sep 02 2014

a(n) = (2^(-2-n)*((7-sqrt(33))^n*(-5+sqrt(33)) + (5+sqrt(33))*(7+sqrt(33))^n)) / sqrt(33). - Colin Barker, Jan 31 2018