login
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.
7
3, 19, 121, 771, 4913, 31307, 199497, 1271251, 8100769, 51620379, 328939577, 2096095523, 13356910353, 85113990379, 542370291241, 3456136077171, 22023471375233, 140339755317947, 894284401724697, 5698631790801091, 36313284928708849, 231398467337757579
OFFSET
1,1
COMMENTS
Horizontally or vertically adjacent entries can differ by at most 1. Diagonally adjacent entries thus differ by at most 2.
LINKS
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.
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
EXAMPLE
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.
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 *)
PROG
(PARI) Vec(x*(3 - 2*x) / (1 - 7*x + 4*x^2) + O(x^30)) \\ Colin Barker, Jan 31 2018
CROSSREFS
Sequence in context: A126809 A340644 A020073 * A163605 A294252 A294253
KEYWORD
nonn,easy
AUTHOR
STATUS
approved