A254126 -id:A254126 - cp's OEIS frontend

A254414 Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 7, 4, 1, 1, 8, 29, 29, 8, 1, 1, 16, 124, 257, 124, 16, 1, 1, 32, 533, 2408, 2408, 533, 32, 1, 1, 64, 2293, 22873, 50128, 22873, 2293, 64, 1, 1, 128, 9866, 217969, 1064576, 1064576, 217969, 9866, 128, 1, 1, 256, 42451, 2078716, 22734496, 50796983, 22734496, 2078716, 42451, 256, 1

Offset: 0

Alois P. Heinz, Jan 30 2015

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

All columns (or rows) are linear recurrences with constant coefficients. An upper bound on the order of the recurrence is A005683(k+2). This upper bound is exact for at least 1 <= k <= 10. - Andrew Howroyd, Dec 23 2019

			Square array A(n,k) begins:
  1,  1,    1,      1,        1,          1,            1, ...
  1,  1,    2,      4,        8,         16,           32, ...
  1,  2,    7,     29,      124,        533,         2293, ...
  1,  4,   29,    257,     2408,      22873,       217969, ...
  1,  8,  124,   2408,    50128,    1064576,     22734496, ...
  1, 16,  533,  22873,  1064576,   50796983,   2441987149, ...
  1, 32, 2293, 217969, 22734496, 2441987149, 264719566561, ...

Liang Kai, Table of n, a(n) for n = 0..1377 (terms 0..495 from Andrew Howroyd)
Wikipedia, Polyomino

Columns (or rows) k=0-7 give: A000012, A011782, A052961, A254124, A254125, A254126, A254458, A254607.
Main diagonal gives: A254127.
Cf. A005683.

step(v,S)={vector(#v, i, sum(j=1, #v, v[j]*2^hammingweight(bitand(S[i], S[j]))))}
mkS(k)={apply(b->bitand(b,2*b+1), [2^(k-1)..2^k-1])}
T(n,k)={if(k<2, if(k==0||n==0, 1, 2^(n-1)), my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v))} \\ Andrew Howroyd, Dec 23 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

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

A254150 Number of independent sets in the generalized Aztec diamond E(L_5,L_{2n-1}).

Original entry on oeis.org

1, 8, 73, 689, 6556, 62501, 596113, 5686112, 54239137, 517383521, 4935293524, 47077513469, 449070034657, 4283656560248, 40861585458553, 389776618229969, 3718059650555596, 35466384896440661, 338312070235103473, 3227141903559443792, 30783545081553045457

Offset: 0

Steve Butler, Jan 26 2015

E(L_5,L_{2n-1}) is the graph with vertices {(a,b) : 1<=a<=5, 1<=b<=2n-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Independent Vertex Set
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).

Row n=3 of A331406.

Cf. A254124, A254125, A254126, A254151, A254152.

Vec((1 - 4*x + x^2)/(1 - 12*x + 24*x^2 - 5*x^3) + O(x^25)) \\ Andrew Howroyd, Jan 16 2020

Empirical g.f.: -(x^2-4*x+1) / (5*x^3-24*x^2+12*x-1). - Colin Barker, Jan 26 2015

The above g.f. is correct. See A331406 for bounds on the order of the recurrence. - Andrew Howroyd, Jan 16 2020

Terms a(12) and beyond from Andrew Howroyd, Jan 15 2020

A254151 Number of independent sets in the generalized Aztec diamond E(L_7,L_{2n-1}).

Original entry on oeis.org

1, 16, 314, 6556, 139344, 2976416, 63663808, 1362242592, 29151501760, 623849225024, 13350628082560, 285709494797952, 6114316283697408, 130849237522680064, 2800235203724240384, 59926350645878761984, 1282452098548524184576, 27445078313878468469760

Offset: 0

Steve Butler, Jan 26 2015

nonn

E(L_7,L_{2n-1}) is the graph with vertices {(a,b) : 1<=a<=7, 1<=b<=2n-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Independent Vertex Set
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).

Row n=4 of A331406.

Cf. A254124, A254125, A254126, A254150, A254152.

LinearRecurrence[{30,-202,396,-248,32},{1,16,314,6556,139344},20] (* Harvey P. Dale, May 31 2024 *)

Vec((1 - 14*x + 36*x^2 - 28*x^3 + 4*x^4)/(1 - 30*x + 202*x^2 - 396*x^3 + 248*x^4 - 32*x^5) + O(x^20)) \\ Andrew Howroyd, Jan 16 2020

Empirical g.f.: -(4*x^4-28*x^3+36*x^2-14*x+1) / (32*x^5-248*x^4+396*x^3-202*x^2+30*x-1). - Colin Barker, Jan 26 2015

The above g.f. is correct. See A331406 for bounds on the order of the recurrence. - Andrew Howroyd, Jan 16 2020

Terms a(12) and beyond from Andrew Howroyd, Jan 15 2020

A254152 Number of independent sets in the generalized Aztec diamond E(L_9,L_{2n-1}).

Original entry on oeis.org

1, 32, 1351, 62501, 2976416, 142999897, 6888568813, 332097693792, 16014193762579, 772279980131297, 37243762479698928, 1796118644459454733, 86619824190256627593, 4177339899819872607008, 201457018240598757372431, 9715496740529686006497709, 468541027322402116068858304

Offset: 0

Steve Butler, Jan 26 2015

nonn

E(L_9,L_{2n-1}) is the graph with vertices {(a,b) : 1<=a<=9, 1<=b<=2n-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Independent Vertex Set
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 (74,-1450,10672,-34214,50814,-34671,9772,-936).

Row n=5 of A331406.

Cf. A254124, A254125, A254126, A254150, A254151.

Vec((1 - 42*x + 433*x^2 - 1745*x^3 + 3002*x^4 - 2275*x^5 + 700*x^6 - 72*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) + O(x^20)) \\ Andrew Howroyd, Jan 16 2020

G.f.: (1 - 42*x + 433*x^2 - 1745*x^3 + 3002*x^4 - 2275*x^5 + 700*x^6 - 72*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). - Andrew Howroyd, Jan 16 2020

a(10)-a(11) corrected and a(12) and beyond from Andrew Howroyd, Jan 15 2020

cp's OEIS Frontend

A254414 Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

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

A254150 Number of independent sets in the generalized Aztec diamond E(L_5,L_{2n-1}).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A254151 Number of independent sets in the generalized Aztec diamond E(L_7,L_{2n-1}).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A254152 Number of independent sets in the generalized Aztec diamond E(L_9,L_{2n-1}).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions