OFFSET
0,2
COMMENTS
a(n) is the number of tilings of a 2 X n rectangle using integer dimension tiles at least one of whose dimensions is 1, so allowable dimensions are 1 X 1, 1 X 2, 1 X 3, 1 X 4, ..., and 2 X 1. - David Callan, Aug 27 2014
a(n+1) counts closed walks on K_2 containing one loop on the index vertex and four loops on the other vertex. Equivalently the (1,1)_entry of A^(n+1) where the adjacency matrix of digraph is A=(1,1;1,4). - David Neil McGrath, Nov 05 2014
A production matrix for the sequence is M =
1, 1, 0, 0, 0, 0, 0, ...
1, 0, 4, 0, 0, 0, 0, ...
1, 0, 0, 4, 0, 0, 0, ...
1, 0, 0, 0, 4, 0, 0, ...
1, 0, 0, 0, 0, 4, 0, ...
1, 0, 0, 0, 0, 0, 4, ...
...
Take powers of M and extract the upper left term, getting the sequence starting (1, 1, 2, 7, 29, 124, ...). - Gary W. Adamson, Jul 22 2016
From Gary W. Adamson, Jul 29 2016: (Start)
The sequence is N=1 in an infinite set obtained from matrix powers of [(1,N); (1,4)], extracting the upper left terms.
The infinite set begins:
N=1 (A052961): 1, 2, 7, 29 124, 533, 2293, ...
N=2 (A052984): 1, 3, 13, 59, 269, 1227, 5597, ...
N=3 (A004253): 1, 4, 19, 91, 436, 2089, 10009, ...
N=4 (A000351): 1, 5, 25, 125, 625, 3125, 15625, ...
N=5 (A015449): 1, 6, 31, 161, 836, 4341, 22541, ...
N=6 (A124610): 1, 7, 37, 199, 1069, 5743, 30853, ...
N=7 (A111363): 1, 8, 43, 239, 1324, 7337, 40653, ...
N=8 (A123270): 1, 9, 49, 281, 1601, 9129, 52049, ...
N=9 (A188168): 1, 10, 55, 325, 1900, 11125, 65125, ...
N=10 (A092164): 1, 11, 61, 371, 2221, 13331, 79981, ...
... (End)
LINKS
Karl V. Keller, Jr., Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1032
Index entries for linear recurrences with constant coefficients, signature (5,-3).
FORMULA
G.f.: (1-3*x)/(1-5*x+3*x^2).
a(n) = 5*a(n-1) - 3*a(n-2), with a(0) = 1, a(1) = 2.
a(n) = Sum_{alpha=RootOf(1-5*z+3*z^2)} (-1 + 9*alpha)*alpha^(-1-n)/13.
E.g.f.: (1 + sqrt(13) + (sqrt(13)-1) * exp(sqrt(13)*x)) / (2*sqrt(13) * exp(((sqrt(13)-5)*x)/2)). - Vaclav Kotesovec, Feb 16 2015
MAPLE
spec:= [S, {S = Sequence(Union(Prod(Sequence(Union(Z, Z, Z)), Z), Z))}, unlabeled ]: seq(combstruct[count ](spec, size = n), n = 0..20);
seq(coeff(series((1-3*x)/(1-5*x+3*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 23 2019
MATHEMATICA
CoefficientList[Series[(1-3x)/(1-5x+3x^2), {x, 0, 30}], x] (* or *) LinearRecurrence[{5, -3}, {1, 2}, 30] (* Harvey P. Dale, Nov 23 2013 *)
PROG
(Magma) I:=[1, 2]; [n le 2 select I[n] else 5*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 17 2014
(PARI) my(x='x+O('x^30)); Vec((1-3*x)/(1-5*x+3*x^2)) \\ G. C. Greubel, Oct 23 2019
(Sage)
def A052961_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P((1-3*x)/(1-5*x+3*x^2)).list()
A052961_list(30) # G. C. Greubel, Oct 23 2019
(GAP) a:=[1, 2];; for n in [3..30] do a[n]:=5*a[n-1]-3*a[n-2]; od; a; # G. C. Greubel, Oct 23 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved