OFFSET
0,3
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.)
LINKS
Steve Butler, Table of n, a(n) for n = 0..15
Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.
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=', ')
CROSSREFS
KEYWORD
nonn
AUTHOR
Steve Butler, Jan 25 2015
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jan 30 2015
STATUS
approved