| Displaying 1-7 of 7 results found.
page
1
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
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
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
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
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.
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
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
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.
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
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.
+10
5
1, 1, 7, 257, 50128, 50796983, 264719566561, 7063448084710944, 963204439792722969647, 670733745303300958404439297, 2384351527902618144856749327661056, 43263422878945294225852497665519673400479, 4006622856873663241294794301627790673728956619649
COMMENTS
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.)
EXAMPLE
a(2)=7 for the following 7 tilings:
_ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_| |_ _| |_|_| | |_| |_| | |_ _| | | |
|_|_| |_|_| |_ _| |_|_| |_|_| |_ _| |_|_|
PROG
(SageMath)
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=', ')
Number of independent sets in the generalized Aztec diamond E(L_5,L_{2n-1}).
+10
4
1, 8, 73, 689, 6556, 62501, 596113, 5686112, 54239137, 517383521, 4935293524, 47077513469, 449070034657, 4283656560248, 40861585458553, 389776618229969, 3718059650555596, 35466384896440661, 338312070235103473, 3227141903559443792, 30783545081553045457
COMMENTS
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.
FORMULA
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
PROG
(PARI) Vec((1 - 4*x + x^2)/(1 - 12*x + 24*x^2 - 5*x^3) + O(x^25)) \\ Andrew Howroyd, Jan 16 2020
Number of independent sets in the generalized Aztec diamond E(L_7,L_{2n-1}).
+10
4
1, 16, 314, 6556, 139344, 2976416, 63663808, 1362242592, 29151501760, 623849225024, 13350628082560, 285709494797952, 6114316283697408, 130849237522680064, 2800235203724240384, 59926350645878761984, 1282452098548524184576, 27445078313878468469760
COMMENTS
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.
FORMULA
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
MATHEMATICA
LinearRecurrence[{30, -202, 396, -248, 32}, {1, 16, 314, 6556, 139344}, 20] (* Harvey P. Dale, May 31 2024 *)
PROG
(PARI) 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
Number of independent sets in the generalized Aztec diamond E(L_9,L_{2n-1}).
+10
4
1, 32, 1351, 62501, 2976416, 142999897, 6888568813, 332097693792, 16014193762579, 772279980131297, 37243762479698928, 1796118644459454733, 86619824190256627593, 4177339899819872607008, 201457018240598757372431, 9715496740529686006497709, 468541027322402116068858304
COMMENTS
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.
FORMULA
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
PROG
(PARI) 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
EXTENSIONS
a(10)-a(11) corrected and a(12) and beyond from Andrew Howroyd, Jan 15 2020
Search completed in 0.007 seconds
|