login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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_{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.

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.

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, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

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=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}

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])))}

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))}

{ 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 12:09 EDT 2020. Contains 336439 sequences. (Running on oeis4.)