|
%I #15 Jan 31 2020 15:36:47
%S 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,
%T 1,64,1351,6556,6556,1351,64,1,1,128,5813,62501,139344,62501,5813,128,
%U 1,1,256,25012,596113,2976416,2976416,596113,25012,256,1
%N Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.
%C The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
%C 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.
%C Equivalently, A(n,m) is the number of independent sets in the generalized Aztec diamond graph E(L_{2n-1}, L_{2m-1}). The E(L_{2n-1},L_{2m-1}) Aztec diamond is the graph with vertices {(a,b) : 1<=a<=2n-1, 1<=b<=2m-1, a+b even and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.
%C All rows (or columns) are linear recurrences with constant coefficients. For n > 0 an upper bound on the order of the recurrence is A005418(n-1), which is the number of binary words of length n up to reflection.
%C 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.
%C 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.
%H Andrew Howroyd, <a href="/A331406/b331406.txt">Table of n, a(n) for n = 0..860</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Independent_set_(graph_theory)">Independent set</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.
%F A(n,m) = A(m,n).
%e Array begins:
%e ===========================================================
%e n\m | 0 1 2 3 4 5 6
%e ----+------------------------------------------------------
%e 0 | 1 1 1 1 1 1 1 ...
%e 1 | 1 2 4 8 16 32 64 ...
%e 2 | 1 4 17 73 314 1351 5813 ...
%e 3 | 1 8 73 689 6556 62501 596113 ...
%e 4 | 1 16 314 6556 139344 2976416 63663808 ...
%e 5 | 1 32 1351 62501 2976416 142999897 6888568813 ...
%e 6 | 1 64 5813 596113 63663808 6888568813 748437606081 ...
%e ...
%e Case A(2,2): the checker board has 5 black squares as shown below.
%e __ __
%e |__|__|__|
%e __|__|__
%e |__| |__|
%e 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.
%o (PARI)
%o step1(v)={vector(#v/2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}
%o step2(v)={vector(#v*2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j<<1)), v[1+j])))}
%o T(n,k)={if(n==0||k==0, 1, my(v=vector(2^k, i, 1)); for(i=2, n, v=step2(step1(v))); vecsum(v))}
%o { for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print) }
%Y Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
%Y Main diagonal is A054867.
%Y Cf. A005418, A005683, A089934, A254414.
%K nonn,tabl
%O 0,5
%A _Andrew Howroyd_, Jan 16 2020
|
