

A331406


Array read by antidiagonals: A(n,m) is the number of ways to place nonadjacent counters on the black squares of a 2n1 X 2m1 checker board.


5



1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 17, 8, 1, 1, 16, 73, 73, 16, 1, 1, 32, 314, 689, 314, 32, 1, 1, 64, 1351, 6556, 6556, 1351, 64, 1, 1, 128, 5813, 62501, 139344, 62501, 5813, 128, 1, 1, 256, 25012, 596113, 2976416, 2976416, 596113, 25012, 256, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
The checker board is such that the black squares are in the corners and adjacent means diagonally adjacent, since the white squares are not included.
Equivalently, A(n,m) is the number of independent sets in the generalized Aztec diamond graph E(L_{2n1}, L_{2m1}). The E(L_{2n1},L_{2m1}) Aztec diamond is the graph with vertices {(a,b) : 1<=a<=2n1, 1<=b<=2m1, a+b even and edges between (a,b) and (c,d) if and only if ab=cd=1.
All rows (or columns) are linear recurrences with constant coefficients. For n > 0 an upper bound on the order of the recurrence is A005418(n1), which is the number of binary words of length n up to reflection.
A stronger upper bound on the recurrence order is A005683(n+2). This upper bound is exact for at least 1 <= n <= 10. This bound follows from considerations about which patterns of counters in a row are redundant because they attack the same points in adjacent rows. For example, the pattern of counters 1101101 is equivalent to 1111111 because they each attack all points in the neighboring rows.
It appears that the denominators for the recurrences are the same as those for the rows and columns of A254414. This suggests there is a connection.


LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..860
Eric Weisstein's World of Mathematics, Independent Vertex Set
Wikipedia, Independent set
Z. Zhang, MerrifieldSimmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625636.


FORMULA

A(n,m) = A(m,n).


EXAMPLE

Array begins:
===========================================================
n\m  0 1 2 3 4 5 6
+
0  1 1 1 1 1 1 1 ...
1  1 2 4 8 16 32 64 ...
2  1 4 17 73 314 1351 5813 ...
3  1 8 73 689 6556 62501 596113 ...
4  1 16 314 6556 139344 2976416 63663808 ...
5  1 32 1351 62501 2976416 142999897 6888568813 ...
6  1 64 5813 596113 63663808 6888568813 748437606081 ...
...
Case A(2,2): the checker board has 5 black squares as shown below.
__ __
______
______
__ __
If a counter is placed on the central square then a counter cannot be placed on the other 4 squares, otherwise counters can be placed in any combination. The total number of arrangements is then 1 + 2^4 = 17, so A(2, 2) = 17.


PROG

(PARI)
step1(v)={vector(#v/2, t, my(i=t1); sum(j=0, #v1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}
step2(v)={vector(#v*2, t, my(i=t1); sum(j=0, #v1, if(!bitand(i, bitor(j, j<<1)), v[1+j])))}
T(n, k)={if(n==0k==0, 1, my(v=vector(2^k, i, 1)); for(i=2, n, v=step2(step1(v))); vecsum(v))}
{ for(n=0, 7, for(k=0, 7, print1(T(n, k), ", ")); print) }


CROSSREFS

Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
Main diagonal is A054867.
Cf. A005418, A005683, A089934, A254414.
Sequence in context: A299906 A117401 A144324 * A034372 A268056 A268079
Adjacent sequences: A331403 A331404 A331405 * A331407 A331408 A331409


KEYWORD

nonn,tabl


AUTHOR

Andrew Howroyd, Jan 16 2020


STATUS

approved



