A033505 -id:A033505 - cp's OEIS frontend

A365967 a(2n) = A030186(n), a(2n+1) = A033505(n).

1, 1, 2, 3, 7, 10, 22, 32, 71, 103, 228, 331, 733, 1064, 2356, 3420, 7573, 10993, 24342, 35335, 78243, 113578, 251498, 365076, 808395, 1173471, 2598440, 3771911, 8352217, 12124128, 26846696, 38970824, 86293865, 125264689, 277376074, 402640763, 891575391

Offset: 0

Greg Dresden, Sep 23 2023

a(n) is the number of ways to tile a double-height board of n cells with squares and dominos. For example, here is the board for n=9:
 _____
|||_||
|||_|||
and here is one of the a(9)=103 possible tilings of this board:
 _____
| |||_|_
|||___|_|.

Index entries for linear recurrences with constant coefficients, signature (0,3,0,1,0,-1).

Cf. A030186, A033505.

a[0] = 1; a[1] = 1; a[2] = 2; a[3] = 3;
a[n_] := a[n] = If[EvenQ[n], a[n-1] + a[n-2] + a[n-3] + a[n-4], a[n-1] + a[n-2]];
Table[a[n],{n,0,30}]

a(n) = 3*a(n-2) + a(n-4) - a(n-6).
a(2*n) = a(2*n-1) + a(2*n-2) + a(2*n-3) + a(2*n-4).
a(2*n+1) = a(2*n) + a(2*n-1).
G.f.: (1+x-x^2)/(1-3*x^2-x^4+x^6).

A030186 a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.

Original entry on oeis.org

1, 2, 7, 22, 71, 228, 733, 2356, 7573, 24342, 78243, 251498, 808395, 2598440, 8352217, 26846696, 86293865, 277376074, 891575391, 2865808382, 9211624463, 29609106380, 95173135221, 305916887580, 983314691581, 3160687827102, 10159461285307, 32655756991442

Offset: 0

Ottavio D'Antona (dantona(AT)dsi.unimi.it)

Number of matchings in ladder graph L_n = P_2 X P_n.
Cycle-path coverings of a family of digraphs.
a(n+1) = Fibonacci(n+1)^2 + Sum_{k=0..n} Fibonacci(k)^2*a(n-k) (with the offset convention Fibonacci(2)=2). - Barry Cipra, Jun 11 2003
Equivalently, ways of paving a 2 X n grid cells using only singletons and dominoes. - Lekraj Beedassy, Mar 25 2005
It is easy to see that the g.f. for indecomposable tilings (pavings) i.e. those that cannot be split vertically into smaller tilings, is g=2x+3x^2+2x^3+2x^4+2x^5+...=x(2+x-x^2)/(1-x); then G.f.=1/(1-g)=(1-x)/(1-3x-x^2+x^3). - Emeric Deutsch, Oct 16 2006
Row sums of A046741. - Emeric Deutsch, Oct 16 2006
Equals binomial transform of A156096. - Gary W. Adamson, Feb 03 2009
a(n) = Lucas(2n) + Sum_{k=2..n-1} Fibonacci(2k-1)*a(n-k). This relationship can be proven by a visual proof using the idea of tiling a 2 X n board with only singletons and dominoes while conditioning on where the vertical dominoes first appear. If there are no vertical dominoes positioned at lengths 2 through n-1, there will be Lucas(2n) ways to tile the board since a complete tour around the board will be made possible. If the first vertical domino appears at length k (where 2 <= k <= n-1) there will be Fibonacci(2k-1)*a(n-k) ways to tile the board. - Rana Ürek, Jun 25 2018

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25.
J. D. E. Konhauser et al., Which Way Did The Bicycle Go? Problem 140 "Count The Tilings" pp. 42; 180-1 Dolciani Math. Exp. No. 18 MAA Washington DC 1996.

Indranil Ghosh, Table of n, a(n) for n = 0..1968 (terms 0..200 from T. D. Noe)
Ottavio M. D'Antona and Emanuele Munarini, The Cycle-path Indicator Polynomial of a Digraph, Advances in Applied Mathematics 25 (2000), 41-56.
Roger C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 473
Matt Katz and Catherine Stenson, Tiling a (2xn)-Board with Squares and Dominoes, JIS 12 (2009) 09.2.2, Table 1.
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Richard M. Low and Ardak Kapbasov, Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 2.
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Richmond B. McQuistan and S. J. Lichtman, Exact recursion relation for (2 × N) arrays of dumbbells, J. Math Phys. 11 (1970), 3095-3099.
László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See pp. 1, 7.
N. J. A. Sloane Notes on A030186 and A033505
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Matching
Yifan Zhang and George Grossman, A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence, J. Int. Seq. 21 (2018), #18.3.3.
Index entries for linear recurrences with constant coefficients, signature (3,1,-1).

Partial sums give A033505.
Column 2 of triangle A210662.
Cf. A054894, A055518, A055519, A088016.
Cf. A156096. - Gary W. Adamson, Feb 03 2009
Bisection (even part) gives A260033.

a:=[1,2,7];; for n in [4..30] do a[n]:=3*a[n-1]+a[n-2]-a[n-3]; od; a; # G. C. Greubel, Sep 27 2019

a030186 n = a030186_list !! n
a030186_list = 1 : 2 : 7 : zipWith (-) (tail $
   zipWith (+) a030186_list $ tail $ map (* 3) a030186_list) a030186_list
-- Reinhard Zumkeller, Oct 20 2011

a[0]:=1: a[1]:=2: a[2]:=7: for n from 3 to 30 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n],n=0..30); # Emeric Deutsch, Oct 16 2006
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <-1|1|3>>^(n+1))[3,2]:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 07 2024

LinearRecurrence[{3,1,-1}, {1,2,7}, 26] (* Robert G. Wilson v, Nov 20 2012 *)
Table[RootSum[1 -# -3#^2 +#^3 &, 9#^n -10#^(n+1) +7#^(n+2) &]/74, {n, 0, 30}] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[(1-x)/(1-3x-x^2+x^3), {x,0,30}], x] (* Eric W. Weisstein, Oct 03 2017 *)

{a(n)=if(n==0,1,if(n==1,2,(sum(k=0, n-1, a(k))^2+sum(k=0, n-1, a(k)^2))/a(n-1)))} \\ Paul D. Hanna, Nov 20 2012

def A030186_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-3*x-x^2+x^3)).list()
A030186_list(30) # G. C. Greubel, Sep 27 2019

G.f.: (1-x)/(1-3*x-x^2+x^3).

a(n) = ( (Sum_{k=0..n-1} a(k))^2 + (Sum_{k=0..n-1} a(k)^2) ) / a(n-1) for n>1 with a(0)=1, a(1)=2 (similar to A088016). - Paul D. Hanna, Nov 20 2012

More terms from James Sellers

Entry revised by N. J. A. Sloane, Feb 13 2002

A089068 a(n) = a(n-1)+a(n-2)+a(n-3)+2 with a(0)=0, a(1)=0 and a(2)=1.

Original entry on oeis.org

0, 0, 1, 3, 6, 12, 23, 43, 80, 148, 273, 503, 926, 1704, 3135, 5767, 10608, 19512, 35889, 66011, 121414, 223316, 410743, 755475, 1389536, 2555756, 4700769, 8646063, 15902590, 29249424, 53798079, 98950095, 181997600, 334745776, 615693473

Offset: 0

Roger L. Bagula, Dec 03 2003

The a(n+2) represent the Kn12 and Kn22 sums of the square array of Delannoy numbers A008288. See A180662 for the definition of these knight and other chess sums. - Johannes W. Meijer, Sep 21 2010

Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Cf. A000931, A000073, A077939, A113300, A001057, A006054, A033505.

Cf. A000073 (Kn11 & Kn21), A089068 (Kn12 & Kn22), A180668 (Kn13 & Kn23), A180669 (Kn14 & Kn24), A180670 (Kn15 & Kn25). - Johannes W. Meijer, Sep 21 2010

Join[{a=0,b=0,c=1},Table[d=a+b+c+2;a=b;b=c;c=d,{n,50}]] (* Vladimir Joseph Stephan Orlovsky, Apr 19 2011 *)
RecurrenceTable[{a[0]==a[1]==0,a[2]==1,a[n]==a[n-1]+a[n-2]+a[n-3]+2}, a[n],{n,40}] (* or *) LinearRecurrence[{2,0,0,-1},{0,0,1,3},40] (* Harvey P. Dale, Sep 19 2011 *)

a(n) = A008937(n-2)+A008937(n-1). - Johannes W. Meijer, Sep 21 2010
a(n) = A018921(n-5)+A018921(n-4), n>4. - Johannes W. Meijer, Sep 21 2010
a(n) = A000073(n+2)-1. - R. J. Mathar, Sep 22 2010
From Johannes W. Meijer, Sep 22 2010: (Start)
a(n) = a(n-1)+A001590(n+1).
a(n) = Sum_{m=0..n} A040000(m)*A000073(n-m).
a(n+2) = Sum_{k=0..floor(n/2)} A008288(n-k+1,k+1).
G.f. = x^2*(1+x)/((1-x)*(1-x-x^2-x^3)). (End)
a(n) = 2*a(n-1)-a(n-4), a(0)=0, a(1)=0, a(2)=1, a(3)=3. - Bruno Berselli, Sep 23 2010

Corrected and information added by Johannes W. Meijer, Sep 22 2010, Oct 22 2010

Definition based on arbitrarily set floating-point precision removed by R. J. Mathar, Sep 30 2010

A102080 Number of matchings in the C_n X P_2 (n-prism) graph.

Original entry on oeis.org

2, 12, 32, 108, 342, 1104, 3544, 11396, 36626, 117732, 378424, 1216380, 3909830, 12567448, 40395792, 129844996, 417363330, 1341539196, 4312135920, 13860583628, 44552347606, 143205490528, 460308235560, 1479577849604, 4755836293842, 15286778495572

Offset: 1

Emeric Deutsch, Dec 29 2004

C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices.
a(n) = sum of row n in A102079.
Prism graphs are defined for n>=3; extended to n=1 using closed form.
Also the Hosoya index of the n-prism graph Y_n. - Eric W. Weisstein, Jul 11 2011

			a(3)=32 because in the graph with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following matchings:
(i) the empty set (1 matching), (ii) any edge (9 matchings), (iii) any two edges from the set {AA',BB',CC'} (3 matchings), (iv) the members of the Cartesian product of {AB,AC,BC}and {A'B',A'C',B'C'} (9 matchings), (v) {AA',BC}, {AA',B'C'}and four more obtained by circular permutations (6 matchings), (vi) {AA',BC,B'C'} and two more obtained by circular permutations (3 matchings), (vii) {AA',BB',CC'} (1 matching).

Colin Barker, Table of n, a(n) for n = 1..1000
H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (Eq. (23) and Table IV).
Eric Weisstein's World of Mathematics, Independent Edge Set.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Prism Graph.
Index entries for linear recurrences with constant coefficients, signature (2,4,0,-1).

Column 2 of A287428.

Cf. A068397, A102079.

a:=[2,12,32,108];; for n in [5..30] do a[n]:=2*a[n-1]+4*a[n-2]-a[n-4]; od; a; # G. C. Greubel, Oct 27 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( 2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3)) )); // G. C. Greubel, Oct 27 2019

a[2]:=12: a[3]:=32: a[4]:=108: a[5]:=342: for n from 6 to 30 do a[n]:=2*a[n-1]+4*a[n-2]-a[n-4] od:seq(a[n],n=2..27);

Table[(-1)^n + RootSum[1 - # - 3 #^2 + #^3 &, #^n &], {n, 30}]
LinearRecurrence[{2, 4, 0, -1}, {2, 12, 32, 108}, 20] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[2(1+4x-2x^3)/(1-2x-4x^2+x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Oct 03 2017 *)

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

def A102080_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3))).list()
a=A102080_list(30); a[1:] # G. C. Greubel, Oct 27 2019

G.f.: 2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3)). - Corrected by Colin Barker, Jan 28 2017
a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for n>4.
a(n) = A033505(n) - 7*A033505(n-2) - (-1)^n. - Ralf Stephan, May 17 2007

A188106 Triangle T(n,k) with the coefficient [x^k] of 1/(1-2*x-x^2+x^3)^(n-k+1) in row n, column k.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 1, 6, 14, 11, 1, 8, 27, 42, 25, 1, 10, 44, 101, 119, 56, 1, 12, 65, 196, 342, 322, 126, 1, 14, 90, 335, 770, 1080, 847, 283, 1, 16, 119, 526, 1495, 2772, 3248, 2180, 636, 1, 18, 152, 777, 2625, 6032, 9366, 9414, 5521, 1429, 1, 20, 189, 1096, 4284, 11718, 22590, 30148, 26517, 13804, 3211

Offset: 0

L. Edson Jeffery, Mar 20 2011

Modified versions of the generating function for D(0)={1,2,5,11,...}=A006054(m+2), m=0,1,2,..., are related to rhombus substitution tilings (see A187068, A187069 and A187070). The columns of the triangle have generating functions 1/(1-x), 2*x/(1-x)^2, x^2*(5-x)/(1-x)^3, x^3*(11-2*x-x^2)/(1-x)^4, x^4*(25-6*x-3*x^2)/(1-x)^5, ..., for which the sum of the signed coefficients in the n-th numerator equals 2^n. The diagonals {1,2,5,...}, {1,4,14,...}, ..., are generated by successive series expansion of F(n+1,x), n=0,1,..., where F(n,x)=1/(1-2*x-x^2+x^3)^n. For example, the second diagonal is {T{1,0},T{2,1},...}={1,4,14,...}=A189426, for which successive partial sums give A189427 (excluding the zero terms). Moreover, the diagonals correspond to successive convolutions of A006054 (= the first diagonal) with itself.

			1;
1, 2;
1, 4, 5;
1, 6, 14, 11;
1, 8, 27, 42, 25;
1, 10, 44, 101, 119, 56;
1, 12, 65, 196, 342, 322, 126;
1, 14, 90, 335, 770, 1080, 847, 283;
1, 16, 119, 526, 1495 ...

Cf. A006054, A033505, A189426, A189427.

A188106 := proc(n,k) 1/(1-2*x-x^2+x^3)^(n-k+1) ; coeftayl(%,x=0,k) ; end proc:
seq(seq(A188106(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Mar 22 2011

Sum_{k=0..n} T(n,k) = A033505(n).
T(n,0) = 1.
T(n,2) = A014106(n-1).
T(n,3) = (n-2)*(4*n^2+2*n-9)/3.
T(n,4) = (n-2)*(n-3)*(2*n+7)*(2*n-3)/6.

a(43) and following corrected by Georg Fischer, Oct 14 2023

A181301 Number of 2-compositions of n having no column with equal entries. A 2-composition of n is a nonnegative matrix with two rows, such that each column has at least one nonzero entry and whose entries sum up to n.

Original entry on oeis.org

1, 2, 6, 20, 64, 206, 662, 2128, 6840, 21986, 70670, 227156, 730152, 2346942, 7543822, 24248256, 77941648, 250529378, 805281526, 2588432308, 8320049072, 26743297998, 85961510758, 276307781200, 888141556360, 2854770939522

Offset: 0

Emeric Deutsch, Oct 12 2010

a(n)=A181299(n,0).

G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, European Journal of Combinatorics, 28, 2007, 1724-1741.

Cf. A181299.

g := (1+z)*(1-z)^2/(1-3*z-z^2+z^3): gser := series(g, z = 0, 30): seq(coeff(gser, z, n), n = 0 .. 27);

G.f. = (1+z)(1-z)^2/(1-3z-z^2+z^3).
a(n) = Sum_{k, 0<=k<=n} A060086(n,k)*2^k. - Philippe Deléham, Feb 24 2012
a(n) = 2*A033505(n-1), n>0. - R. J. Mathar, Jul 24 2022

A316726 The number of ways to tile (with squares and rectangles) a 2 X (n+2) strip with the upper left and upper right squares removed.

Original entry on oeis.org

2, 4, 15, 46, 150, 480, 1545, 4964, 15958, 51292, 164871, 529946, 1703418, 5475328, 17599457, 56570280, 181834970, 584475732, 1878691887, 6038716422, 19410365422, 62391120800, 200545011401, 644615789580, 2072001259342, 6660074556204, 21407609138375

Offset: 0

Zijing Wu, Jul 11 2018

Each number in the sequence is the partial sum of A033505 (n starts at 0, each number add one if n is even). We can also find the recursion relation a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for the sequence, which can be proved by induction.

			For n=4, a(4) = 150 = 2*a(3) + 4*a(2) - a(0).

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,4,0,-1).

Cf. A033505, A030186.

CoefficientList[ Series[(-x^2 + 1)/(x^4 - 4x^2 - 2x + 1), {x, 0, 27}], x] (* or *) LinearRecurrence[{2, 4, 0, -1}, {2, 4, 15, 46}, 27] (* Robert G. Wilson v, Jul 15 2018 *)

Vec((2 - x^2) / ((1 + x)*(1 - 3*x - x^2 + x^3)) + O(x^30)) \\ Colin Barker, Jul 12 2018

a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for n>=4.
G.f.: (2 - x^2) / ((1 + x)*(1 - 3*x - x^2 + x^3)). - Colin Barker, Jul 12 2018
a(n) = A030186(n) + 2*A033505(n-1) + a(n-2). - Greg Dresden and Ge Ma, Jul 12 2025

More terms from Colin Barker, Jul 12 2018

A183712 1/20 of the number of (n+1) X 3 0..4 arrays with every 2 X 2 subblock strictly increasing clockwise or counterclockwise with one decrease.

Original entry on oeis.org

5, 17, 54, 174, 559, 1797, 5776, 18566, 59677, 191821, 616574, 1981866, 6370351, 20476345, 65817520, 211558554, 680016837, 2185791545, 7025832918, 22583273462, 72589861759, 233327025821, 749987665760, 2410700161342, 7748761123965, 24906995867477

Offset: 1

R. H. Hardin, Jan 06 2011

Column 2 of A183719. [Corrected by M. F. Hasler, Oct 07 2014]
This sequence counts closed walks of length (n+2) at the vertex of a triangle, to which a loop has been added to one of the remaining vertices and two loops has been added to the third vertex. - David Neil McGrath, Sep 04 2014
From Greg Dresden, Mar 02 2025: (Start)
a(n) is the number of ways to tile, with squares and dominoes, a 2 X n board with two extra spaces at the end. Here is the board for n=3:
    ___
   |||_| 
   |||_|||,
and here is one of the a(3)=54 possible tilings of this board:
    ___
   |_| |_
   |||_|_|.
Compare to A033505 (tilings of 2 X n board with one extra space at the end) and A030186 (tilings of 2 X n board with no extra spaces at the end). (End)

			Some solutions for 5 X 3:
..0..1..4....1..2..0....4..0..4....4..3..4....4..0..4....1..4..0....3..4..2
..3..2..3....0..3..4....2..1..3....0..2..0....3..2..3....2..3..1....1..0..1
..4..1..0....1..2..1....4..0..4....4..3..4....0..1..0....0..4..0....2..4..3
..3..2..3....0..3..4....3..2..3....0..2..1....4..2..3....1..3..1....1..0..1
..4..0..4....1..2..1....4..1..0....4..3..0....0..1..0....0..4..0....2..3..2
...
...R..L.......R..L.......R..L.......L..R.......R..L.......L..R.......R..L...
...L..R.......L..R.......L..R.......R..L.......L..R.......R..L.......L..R...
...R..L.......R..L.......R..L.......L..R.......R..L.......L..R.......R..L...
...L..R.......L..R.......L..R.......R..L.......L..R.......R..L.......L..R...

R. H. Hardin, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (3,1,-1).

Cf. A183727, A183719, A030186, A033505.

a(n)=([0,1,1;1,1,1;1,1,2]^(n+2))[1,1] \\ Charles R Greathouse IV, Sep 15 2014

Vec(x*(5+2*x-2*x^2)/(1-3*x-x^2+x^3) + O(x^50)) \\ Colin Barker, Mar 16 2016

a(n) = 3*a(n-1) + a(n-2) - a(n-3).
The top left element of A^(n+2) where A=(0,1,1;1,1,1;1,1,2). - David Neil McGrath, Sep 04 2014
a(n) ~ c*k^n where k = 1.629316... is the largest root of x^3 - 3x^2 - x + 1 and c = 1.6293... is conjecturally the largest root of 148x^3 - 296x^2 + 90x - 1. - Charles R Greathouse IV, Sep 15 2014
G.f.: x*(5+2*x-2*x^2) / (1-3*x-x^2+x^3). - Colin Barker, Mar 16 2016
a(n) = A030186(n) + A033505(n). - Greg Dresden, Mar 02 2025

A220563 Number of ways to reciprocally link elements of an 2 X n array either to themselves or to exactly one horizontal or antidiagonal neighbor.

Original entry on oeis.org

1, 5, 14, 47, 149, 481, 1544, 4965, 15957, 51293, 164870, 529947, 1703417, 5475329, 17599456, 56570281, 181834969, 584475733, 1878691886, 6038716423, 19410365421, 62391120801, 200545011400, 644615789581, 2072001259341, 6660074556205

Offset: 1

R. H. Hardin, Dec 16 2012

Row 2 of A220562.
From Wajdi Maaloul, Jul 04 2022: (Start)
For n > 0, a(n) is the number of ways to tile the S-shaped figure of length n below with squares and dominoes. For instance, a(4) is the number of ways to tile this figure with squares and dominoes.
      _ _
   |||_||
     |||_|_|
(End)

			Some solutions for n=3, 0=self, 3=ne, 4=w, 6=e, 7=sw (reciprocal directions total 10):
  0 6 4   0 0 0   0 7 0   6 4 0   0 0 0   0 7 0   0 6 4
  0 6 4   0 0 0   3 6 4   0 0 0   0 6 4   3 0 0   0 0 0

R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (2,4,0,-1).

Cf. A220562.

a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4).
G.f.: x*(1 + 3*x - x^3) / ((1 + x)*(1 - 3*x - x^2 + x^3)). - Colin Barker, Jul 31 2018
For n>0, a(n) = A316726(n+1) - A033505(n+1). - Wajdi Maaloul, Jul 04 2022

A061534 Expansion of (1-x^2)/(1-3*x-x^2+x^3).

Original entry on oeis.org

1, 3, 9, 29, 93, 299, 961, 3089, 9929, 31915, 102585, 329741, 1059893, 3406835, 10950657, 35198913, 113140561, 363669939, 1168951465, 3757383773, 12077432845, 38820730843, 124782241601, 401090022801, 1289231579161, 4144002518683, 13320149112409

Offset: 0

Henry Bottomley, May 16 2001

The number of tilings of a 2*n grid using dominoes and singletons with two horizontal dominoes or one vertical domino in the two rightmost squares. - John M. Campbell, Mar 05 2011

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1056
Index entries for linear recurrences with constant coefficients, signature (3,1,-1).

Cf. A033505.

Vec(-(x-1)*(x+1)/(x^3-x^2-3*x+1)  + O(x^100)) \\ Colin Barker, Sep 13 2014

a(n) = 3*a(n-1)+a(n-2)-a(n-3) for n>3. - Colin Barker, Sep 13 2014
G.f.: -(x-1)*(x+1) / (x^3-x^2-3*x+1). - Colin Barker, Sep 13 2014
a(n) = A033505(n)-A033505(n-2). - R. J. Mathar, Oct 24 2015

cp's OEIS Frontend

A365967 a(2*n) = A030186(n), a(2*n+1) = A033505(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A030186 a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A089068 a(n) = a(n-1)+a(n-2)+a(n-3)+2 with a(0)=0, a(1)=0 and a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102080 Number of matchings in the C_n X P_2 (n-prism) graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A188106 Triangle T(n,k) with the coefficient [x^k] of 1/(1-2*x-x^2+x^3)^(n-k+1) in row n, column k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A181301 Number of 2-compositions of n having no column with equal entries. A 2-composition of n is a nonnegative matrix with two rows, such that each column has at least one nonzero entry and whose entries sum up to n.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple

Formula

A316726 The number of ways to tile (with squares and rectangles) a 2 X (n+2) strip with the upper left and upper right squares removed.

Views

Author

Keywords

A365967 a(2n) = A030186(n), a(2n+1) = A033505(n).