A254127 - OEIS

%I #28 May 31 2024 14:42:54

%S 1,1,7,257,50128,50796983,264719566561,7063448084710944,

%T 963204439792722969647,670733745303300958404439297,

%U 2384351527902618144856749327661056,43263422878945294225852497665519673400479,4006622856873663241294794301627790673728956619649

%N 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.

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

%H Steve Butler, <a href="/A254127/b254127.txt">Table of n, a(n) for n = 0..15</a>

%H Z. Zhang, <a href="http://match.pmf.kg.ac.rs/electronic_versions/Match56/n3/match56n3_625-636.pdf">Merrifield-Simmons index of generalized Aztec diamond and related graphs</a>, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

%e a(2)=7 for the following 7 tilings:

%e    _ _   _ _   _ _   _ _   _ _   _ _   _ _

%e   |_|_| |_ _| |_|_| | |_| |_| | |_ _| | | |

%e   |_|_| |_|_| |_ _| |_|_| |_|_| |_ _| |_|_|

%o (SageMath)

%o def matrix_entry(L1, L2, n):

%o     tally=0

%o     for i in range(n-1):

%o         if (not i in L1) and (not i in L2) and (not i+1 in L1) and (not i+1 in L2):

%o             tally+=1

%o     return 2^tally

%o def a(n):

%o     index_set={}

%o     counter=0

%o     for C in Combinations(n):

%o         index_set[counter]=C

%o         counter+=1

%o     current_v=[0]*counter

%o     current_v[0]=1

%o     for t in range(n):

%o         new_v=[0]*counter

%o         for i in range(counter):

%o             for j in range(counter):

%o                 new_v[i]+=current_v[j]*matrix_entry(index_set[I], index_set[j], n)

%o         current_v=new_v

%o     return current_v[0]

%o for n in range(0, 10):

%o     print(a(n), end=', ')

%Y Cf. A052961, A254124, A254125, A254126.

%Y Main diagonal of A254414.

%K nonn

%O 0,3

%A _Steve Butler_, Jan 25 2015

%E a(0)=1 prepended by _Alois P. Heinz_, Jan 30 2015