cp's OEIS Frontend

A331406 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.

%I A331406 #20 Feb 16 2025 08:33:59
%S A331406 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 A331406 1,64,1351,6556,6556,1351,64,1,1,128,5813,62501,139344,62501,5813,128,
%U A331406 1,1,256,25012,596113,2976416,2976416,596113,25012,256,1
%N A331406 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 A331406 The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
%C A331406 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 A331406 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 A331406 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 A331406 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 A331406 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 A331406 Andrew Howroyd, <a href="/A331406/b331406.txt">Table of n, a(n) for n = 0..860</a>
%H A331406 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H A331406 Wikipedia, <a href="https://en.wikipedia.org/wiki/Independent_set_(graph_theory)">Independent set</a>
%H A331406 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 A331406 A(n,m) = A(m,n).
%e A331406 Array begins:
%e A331406 ===========================================================
%e A331406 n\m | 0  1    2      3        4          5            6
%e A331406 ----+------------------------------------------------------
%e A331406   0 | 1  1    1      1        1          1            1 ...
%e A331406   1 | 1  2    4      8       16         32           64 ...
%e A331406   2 | 1  4   17     73      314       1351         5813 ...
%e A331406   3 | 1  8   73    689     6556      62501       596113 ...
%e A331406   4 | 1 16  314   6556   139344    2976416     63663808 ...
%e A331406   5 | 1 32 1351  62501  2976416  142999897   6888568813 ...
%e A331406   6 | 1 64 5813 596113 63663808 6888568813 748437606081 ...
%e A331406   ...
%e A331406 Case A(2,2): the checker board has 5 black squares as shown below.
%e A331406       __    __
%e A331406      |__|__|__|
%e A331406       __|__|__
%e A331406      |__|  |__|
%e A331406 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 A331406 (PARI)
%o A331406 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 A331406 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 A331406 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 A331406 { for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print) }
%Y A331406 Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
%Y A331406 Main diagonal is A054867.
%Y A331406 Cf. A005418, A005683, A089934, A254414.
%K A331406 nonn,tabl
%O A331406 0,5
%A A331406 _Andrew Howroyd_, Jan 16 2020