A254414 -id:A254414 - cp's OEIS frontend

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

1, 2, 7, 29, 124, 533, 2293, 9866, 42451, 182657, 785932, 3381689, 14550649, 62608178, 269388943, 1159120181, 4987434076, 21459809837, 92336746957, 397304305274, 1709511285499, 7355643511673, 31649683701868, 136181487974321, 585958388766001, 2521247479907042

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

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)

Karl V. Keller, Jr., Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1032
Kai Liang, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698, March 2025.
Index entries for linear recurrences with constant coefficients, signature (5,-3).

Column k=2 of A254414.

Cf. A000351, A004253, A015449, A052984, A092164, A111363, A123270, A124610, A188168.

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

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

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

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 *)

my(x='x+O('x^30)); Vec((1-3*x)/(1-5*x+3*x^2)) \\ G. C. Greubel, Oct 23 2019

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

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
a(n) = A116415(n) - 3*A116415(n-1). - R. J. Mathar, Feb 27 2019

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.

Original entry on oeis.org

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

Offset: 0

Steve Butler, Jan 25 2015

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.

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).

Cf. A052961, A254125, A254126, A254127.

Column k=3 of A254414.

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

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

A254125 The number of tilings of a 4 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, 4 X 1.

Original entry on oeis.org

1, 8, 124, 2408, 50128, 1064576, 22734496, 486248000, 10404289216, 222647030144, 4764694602112, 101966374503680, 2182126445631232, 46698521255409152, 999370260391863808, 21386993399983588352, 457691719382960757760, 9794818132582234683392

Offset: 0

Steve Butler, Jan 25 2015

Let G_n be the graph with vertices {(a,b) : 1<=a<=7, 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.

Colin Barker, Table of n, a(n) for n = 0..750
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 (30,-202,396,-248,32).

Cf. A052961, A254124, A254126, A254127.

Column k=4 of A254414.

Vec((1-22*x+86*x^2-92*x^3+16*x^4)/(1-30*x+202*x^2-396*x^3 +248*x^4-32*x^5) + O(x^30)) \\ Michel Marcus, Jan 26 2015

G.f.: (1 - 22x + 86x^2 - 92x^3 + 16x^4)/(1 - 30x + 202x^2 - 396x^3 + 248x^4 - 32x^5).

a(n) = 30*a(n-1) - 202*a(n-2) + 396*a(n-3) - 248*a(n-4) + 32*a(n-5) for n>4. - Colin Barker, Jun 07 2020

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

Original entry on oeis.org

1, 16, 533, 22873, 1064576, 50796983, 2441987149, 117656540512, 5672528575545, 273541357254277, 13191518965300160, 636171495829068099, 30680036092304563369, 1479579136691648516016, 71354395560692698401005, 3441147782121276015384833, 165953315828852845775456128

Offset: 0

Steve Butler, Jan 25 2015

Let G_n be the graph with vertices {(a,b) : 1<=a<=9, 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.

Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

Cf. A052961, A254124, A254125, A254127.

Column k=5 of A254414.

G.f: (1 - 58*x + 799*x^2 - 4041*x^3 + 8286*x^4 - 7357*x^5 + 2660*x^6 - 312*x^7)/(1 - 74*x + 1450*x^2 - 10672*x^3 + 34214*x^4 - 50814*x^5 + 34671*x^6 - 9772*x^7 + 936*x^8).

A254127 The number of tilings of an n X n rectangle using integer length rectangles with at least one side of length 1, i.e., tiles are of size (1 X i) or (i X 1) with 1<=i<=n.

Original entry on oeis.org

1, 1, 7, 257, 50128, 50796983, 264719566561, 7063448084710944, 963204439792722969647, 670733745303300958404439297, 2384351527902618144856749327661056, 43263422878945294225852497665519673400479, 4006622856873663241294794301627790673728956619649

Offset: 0

Steve Butler, Jan 25 2015

nonn

Let R(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y|<=n+1, and let two squares be independent if they do not share a common edge. Then a(n) is the number of ways to pick a set of independent cell(s) in R(n). (Note R(n) is also known as the Aztec diamond.)

			a(2)=7 for the following 7 tilings:
   _ _   _ _   _ _   _ _   _ _   _ _   _ _
  |_|_| |_ _| |_|_| | |_| |_| | |_ _| | | |
  |_|_| |_|_| |_ _| |_|_| |_|_| |_ _| |_|_|

Liang Kai, Table of n, a(n) for n = 0..27 (terms 0..15 from Steve Butler)
Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

Cf. A052961, A254124, A254125, A254126.

Main diagonal of A254414.

def matrix_entry(L1, L2, n):
    tally=0
    for i in range(n-1):
        if (not i in L1) and (not i in L2) and (not i+1 in L1) and (not i+1 in L2):
            tally+=1
    return 2^tally
def a(n):
    index_set={}
    counter=0
    for C in Combinations(n):
        index_set[counter]=C
        counter+=1
    current_v=[0]*counter
    current_v[0]=1
    for t in range(n):
        new_v=[0]*counter
        for i in range(counter):
            for j in range(counter):
                new_v[i]+=current_v[j]*matrix_entry(index_set[I], index_set[j], n)
        current_v=new_v
    return current_v[0]
for n in range(0, 10):
    print(a(n), end=', ')

a(0)=1 prepended by Alois P. Heinz, Jan 30 2015

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 17, 8, 1, 1, 16, 73, 73, 16, 1, 1, 32, 314, 689, 314, 32, 1, 1, 64, 1351, 6556, 6556, 1351, 64, 1, 1, 128, 5813, 62501, 139344, 62501, 5813, 128, 1, 1, 256, 25012, 596113, 2976416, 2976416, 596113, 25012, 256, 1

Offset: 0

Andrew Howroyd, Jan 16 2020

The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
The checker board is such that the black squares are in the corners and adjacent means diagonally adjacent, since the white squares are not included.
Equivalently, A(n,m) is the number of independent sets in the generalized Aztec diamond graph E(L_{2n-1}, L_{2m-1}). The E(L_{2n-1},L_{2m-1}) Aztec diamond is the graph with vertices {(a,b) : 1<=a<=2n-1, 1<=b<=2m-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.
All rows (or columns) are linear recurrences with constant coefficients. For n > 0 an upper bound on the order of the recurrence is A005418(n-1), which is the number of binary words of length n up to reflection.
A stronger upper bound on the recurrence order is A005683(n+2). This upper bound is exact for at least 1 <= n <= 10. This bound follows from considerations about which patterns of counters in a row are redundant because they attack the same points in adjacent rows. For example, the pattern of counters 1101101 is equivalent to 1111111 because they each attack all points in the neighboring rows.
It appears that the denominators for the recurrences are the same as those for the rows and columns of A254414. This suggests there is a connection.

			Array begins:
===========================================================
n\m | 0  1    2      3        4          5            6
----+------------------------------------------------------
  0 | 1  1    1      1        1          1            1 ...
  1 | 1  2    4      8       16         32           64 ...
  2 | 1  4   17     73      314       1351         5813 ...
  3 | 1  8   73    689     6556      62501       596113 ...
  4 | 1 16  314   6556   139344    2976416     63663808 ...
  5 | 1 32 1351  62501  2976416  142999897   6888568813 ...
  6 | 1 64 5813 596113 63663808 6888568813 748437606081 ...
  ...
Case A(2,2): the checker board has 5 black squares as shown below.
      __    __
     |__|__|__|
      __|__|__
     |__|  |__|
If a counter is placed on the central square then a counter cannot be placed on the other 4 squares, otherwise counters can be placed in any combination. The total number of arrangements is then 1 + 2^4 = 17, so A(2, 2) = 17.

Andrew Howroyd, Table of n, a(n) for n = 0..860
Eric Weisstein's World of Mathematics, Independent Vertex Set
Wikipedia, Independent set
Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
Main diagonal is A054867.
Cf. A005418, A005683, A089934, A254414.

step1(v)={vector(#v/2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}
step2(v)={vector(#v*2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j<<1)), v[1+j])))}
T(n,k)={if(n==0||k==0, 1, my(v=vector(2^k, i, 1)); for(i=2, n, v=step2(step1(v))); vecsum(v))}
{ for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print) }

A(n,m) = A(m,n).

A254458 Number of tilings of a 6 X n rectangle using polyominoes of shape I.

Original entry on oeis.org

1, 32, 2293, 217969, 22734496, 2441987149, 264719566561, 28778500622048, 3131382012183077, 340819280011906449, 37097936406550231392, 4038192819517826461181, 439569960022854881087873, 47848695174956866013911072, 5208498569279829885262307157

Offset: 0

Alois P. Heinz, Jan 30 2015

nonn

A polyomino of shape I is a rectangle of width 1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Polyomino

Column k=6 of A254414.

G.f.: (1 - 153*x + 6777*x^2 - 132415*x^3 + 1336362*x^4 - 7606262*x^5 + 25527903*x^6 - 51325185*x^7 + 61507605*x^8 - 42648785*x^9 + 16029360*x^10 - 2890728*x^11 + 181440*x^12)/(1 - 185*x + 10404*x^2 - 259107*x^3 + 3361183*x^4 - 24886632*x^5 + 110360811*x^6 - 299572675*x^7 + 499926324*x^8 - 508443601*x^9 + 305734685*x^10 - 101727600*x^11 + 16409736*x^12 - 907200*x^13). - Andrew Howroyd, Dec 23 2019

A254607 Number of tilings of a 7 X n rectangle using polyominoes of shape I.

Original entry on oeis.org

1, 64, 9866, 2078716, 486248000, 117656540512, 28778500622048, 7063448084710944, 1735575086258267968, 426602245391808219456, 104870171042459607741312, 25780811901305515395438592, 6337913024506813766449064064, 1558108119479642808250383381248, 383044676600298851289615284801792

Offset: 0

Alois P. Heinz, Feb 02 2015

nonn

A polyomino of shape I is a rectangle of width 1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Polyomino

Column k=7 of A254414.

Terms a(11) and beyond from Andrew Howroyd, Dec 23 2019

A334617 a(n) is the number of ways to tile a size n staircase polyomino with staircase polyominoes.

Original entry on oeis.org

1, 2, 8, 57, 806, 20840, 1038266, 97115638, 17213517207, 5768580741287

Offset: 1

Peter Kagey, Sep 08 2020

A size-n staircase polynomo is a polyomino consisting of n left-aligned rows in increasing length of 1, 2, ..., n. Rotations of staircase polyominoes are also polyominoes.

			For n = 3 the a(3) = 8 tilings are:
+---+          +---+          +---+          +---+
|   |          |   |          |   |          |   |
+---+---+      +   +---+      +---+---+      +---+---+
|   |   |      |       |      |   |   |      |   |   |
+---+---+---+, +---+---+---+, +   +---+---+, +---+   +---+,
|   |   |   |  |   |   |   |  |       |   |  |   |       |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
+---+          +---+          +---+          +---+
|   |          |   |          |   |          |   |
+---+---+      +---+---+      +---+---+      +   +---+
|       |      |       |      |   |   |      |       |
+---+   +---+, +   +---+---+, +---+   +---+, +       +---+.
|   |   |   |  |   |   |   |  |       |   |  |           |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

Code Golf Stack Exchange user "Bubbler", Tiling a staircase with staircases.

Cf. A000105, A045846, A219924, A254414, A335547.

a(8) from Seiichi Manyama, Sep 09 2020

a(9)-a(10) from Bert Dobbelaere, Sep 12 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A254125 The number of tilings of a 4 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, 4 X 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A254127 The number of tilings of an n X n rectangle using integer length rectangles with at least one side of length 1, i.e., tiles are of size (1 X i) or (i X 1) with 1<=i<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Extensions

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A254458 Number of tilings of a 6 X n rectangle using polyominoes of shape I.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A254607 Number of tilings of a 7 X n rectangle using polyominoes of shape I.

Views

Author

Keywords

Comments

Links

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