A254124 The number of tilings of a 3 X n rectangle using integer length rectangles with at least one side of length 1, i.e., tiles are 1 X 1, 1 X 2, ..., 1 X n, 2 X 1, 3 X 1.

1, 4, 29, 257, 2408, 22873, 217969, 2078716, 19827701, 189133073, 1804125632, 17209452337, 164160078241, 1565914710964, 14937181915469, 142485030313697, 1359157571347928, 12964936038223753, 123671875897903249, 1179699833714208556, 11253097663211943461

Offset: 0

Author

Steve Butler, Jan 25 2015

Keywords

• nonn
• easy

Comments

Let G_n be the graph with vertices {(a,b) : 1<=a<=5, 1<=b<=2n-1, a+b odd} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1. Then a(n) is the number of independent sets in G_n.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.
• Index entries for linear recurrences with constant coefficients, signature (12,-24,5).

Crossrefs

Cf. A052961, A254125, A254126, A254127.

Column k=3 of A254414.

Programs

PARI

Vec((1-8*x+5*x^2)/(1-12*x+24*x^2-5*x^3) + O(x^30)) \\ Michel Marcus, Jan 26 2015

Formula

G.f.: (1 - 8*x + 5*x^2)/(1 - 12*x + 24*x^2 - 5*x^3).

a(n) = 12*a(n-1) - 24*a(n-2) + 5*a(n-3) for n > 2. - Colin Barker, Jun 07 2020