cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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.

Original entry on oeis.org

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
Offset: 0

Views

Author

Andrew Howroyd, Jan 16 2020

Keywords

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.

Examples

			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.

Links

Crossrefs

Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
Main diagonal is A054867.
Cf. A005418, A005683, A089934, A254414.

Programs

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

Formula

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

A254151 Number of independent sets in the generalized Aztec diamond E(L_7,L_{2n-1}).

Original entry on oeis.org

1, 16, 314, 6556, 139344, 2976416, 63663808, 1362242592, 29151501760, 623849225024, 13350628082560, 285709494797952, 6114316283697408, 130849237522680064, 2800235203724240384, 59926350645878761984, 1282452098548524184576, 27445078313878468469760
Offset: 0

Views

Author

Steve Butler, Jan 26 2015

Keywords

Comments

E(L_7,L_{2n-1}) is the graph with vertices {(a,b) : 1<=a<=7, 1<=b<=2n-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.

Links

Crossrefs

Row n=4 of A331406.
Cf. A254124, A254125, A254126, A254150, A254152.

Programs

  • Mathematica
    LinearRecurrence[{30,-202,396,-248,32},{1,16,314,6556,139344},20] (* Harvey P. Dale, May 31 2024 *)
  • PARI
    Vec((1 - 14*x + 36*x^2 - 28*x^3 + 4*x^4)/(1 - 30*x + 202*x^2 - 396*x^3 + 248*x^4 - 32*x^5) + O(x^20)) \\ Andrew Howroyd, Jan 16 2020

Formula

Empirical g.f.: -(4*x^4-28*x^3+36*x^2-14*x+1) / (32*x^5-248*x^4+396*x^3-202*x^2+30*x-1). - Colin Barker, Jan 26 2015
The above g.f. is correct. See A331406 for bounds on the order of the recurrence. - Andrew Howroyd, Jan 16 2020

Extensions

Terms a(12) and beyond from Andrew Howroyd, Jan 15 2020

A254152 Number of independent sets in the generalized Aztec diamond E(L_9,L_{2n-1}).

Original entry on oeis.org

1, 32, 1351, 62501, 2976416, 142999897, 6888568813, 332097693792, 16014193762579, 772279980131297, 37243762479698928, 1796118644459454733, 86619824190256627593, 4177339899819872607008, 201457018240598757372431, 9715496740529686006497709, 468541027322402116068858304
Offset: 0

Views

Author

Steve Butler, Jan 26 2015

Keywords

Comments

E(L_9,L_{2n-1}) is the graph with vertices {(a,b) : 1<=a<=9, 1<=b<=2n-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.

Links

Crossrefs

Row n=5 of A331406.
Cf. A254124, A254125, A254126, A254150, A254151.

Programs

  • PARI
    Vec((1 - 42*x + 433*x^2 - 1745*x^3 + 3002*x^4 - 2275*x^5 + 700*x^6 - 72*x^7)/(1 - 74*x + 1450*x^2 - 10672*x^3 + 34214*x^4 - 50814*x^5 + 34671*x^6 - 9772*x^7 + 936*x^8) + O(x^20)) \\ Andrew Howroyd, Jan 16 2020

Formula

G.f.: (1 - 42*x + 433*x^2 - 1745*x^3 + 3002*x^4 - 2275*x^5 + 700*x^6 - 72*x^7)/(1 - 74*x + 1450*x^2 - 10672*x^3 + 34214*x^4 - 50814*x^5 + 34671*x^6 - 9772*x^7 + 936*x^8). - Andrew Howroyd, Jan 16 2020

Extensions

a(10)-a(11) corrected and a(12) and beyond from Andrew Howroyd, Jan 15 2020
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.