cp's OEIS Frontend

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.

%I A138977 #23 Nov 30 2023 10:39:51
%S A138977 3,19,121,771,4913,31307,199497,1271251,8100769,51620379,328939577,
%T A138977 2096095523,13356910353,85113990379,542370291241,3456136077171,
%U A138977 22023471375233,140339755317947,894284401724697,5698631790801091,36313284928708849,231398467337757579
%N 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.
%C A138977 Horizontally or vertically adjacent entries can differ by at most 1. Diagonally adjacent entries thus differ by at most 2.
%H A138977 Alois P. Heinz, <a href="/A138977/b138977.txt">Table of n, a(n) for n = 1..1000</a>
%H A138977 Michael Han, Sycamore Herlihy, Kirsti Kuenzel, Daniel Martin, and Rachel Schmidt, <a href="https://arxiv.org/abs/2311.15334">The number of independent sets in bipartite graphs and benzenoids</a>, arXiv:2311.15334 [math.CO], 2023. See p. 13.
%H A138977 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (7,-4).
%F A138977 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).
%F A138977 G.f.: x*(3 - 2*x) / (1 - 7*x + 4*x^2). - _N. J. A. Sloane_, Apr 06 2008
%F A138977 a(n+2) = 7*a(n+1) - 4*a(n) for n >= 2. - _Robert Israel_, Sep 02 2014
%F A138977 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
%e A138977 a(1) = 3:
%e A138977 |1|1|1|
%e A138977 |0|1|2|
%e A138977 a(2) = 19:
%e A138977 |10|11|12| |10|11|12| |10|11|12|
%e A138977 |0*|0*|01| |1*|1*|1*| |21|2*|2*|
%e A138977 (3) (2)(1) (2) (3)(2) (1) (2)(3), total 19.
%p A138977 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}):
%p A138977 seq(a(n),n=1..100); # _Robert Israel_, Sep 02 2014
%t A138977 LinearRecurrence[{7, -4}, {3, 19}, 22] (* _Jean-François Alcover_, Apr 30 2019 *)
%o A138977 (PARI) Vec(x*(3 - 2*x) / (1 - 7*x + 4*x^2) + O(x^30)) \\ _Colin Barker_, Jan 31 2018
%Y A138977 Cf. A138978, A138979.
%K A138977 nonn,easy
%O A138977 1,1
%A A138977 _Wayne VanWeerthuizen_, Apr 05 2008