A254127 -id:A254127

Search: a254127 -id:a254127

Displaying 1-4 of 4 results found.

page 1

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.

+10
10

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..495

Wikipedia, Polyomino

EXAMPLE

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

PROG

(PARI)

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

CROSSREFS

Columns (or rows) k=0-7 give: A000012, A011782, A052961, A254124, A254125, A254126, A254458, A254607.

Main diagonal gives: A254127.

Cf. A005683.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jan 30 2015

STATUS

approved

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.

+10
8

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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

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

PROG

(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

CROSSREFS

Cf. A052961, A254125, A254126, A254127.

Column k=3 of A254414.

KEYWORD

nonn,easy

AUTHOR

Steve Butler, Jan 25 2015

STATUS

approved

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.

+10
8

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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.

LINKS

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

FORMULA

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

PROG

(PARI) 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

CROSSREFS

Cf. A052961, A254124, A254126, A254127.

Column k=4 of A254414.

KEYWORD

nonn,easy

AUTHOR

Steve Butler, Jan 25 2015

STATUS

approved

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.

+10
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..16.

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

FORMULA

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

CROSSREFS

Cf. A052961, A254124, A254125, A254127.

Column k=5 of A254414.

KEYWORD

nonn,easy

AUTHOR

Steve Butler, Jan 25 2015

STATUS

approved

page 1

Search completed in 0.006 seconds