A089934 -id:A089934 - cp's OEIS frontend

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

0, 1, 1, 1, 7, 1, 2, 43, 43, 2, 3, 277, 969, 277, 3, 5, 1777, 23663, 23663, 1777, 5, 8, 11407, 571099, 2180738, 571099, 11407, 8, 13, 73219, 13807469, 198906617, 198906617, 13807469, 73219, 13, 21, 469981, 333735575, 18169793971, 68534828391, 18169793971, 333735575, 469981, 21

Offset: 1

Andrew Howroyd, May 15 2017

			Table starts:
======================================================================
m\n| 1     2        3           4              5                 6
---|------------------------------------------------------------------
1  | 0     1        1           2              3                 5 ...
2  | 1     7       43         277           1777             11407 ...
3  | 1    43      969       23663         571099          13807469 ...
4  | 2   277    23663     2180738      198906617       18169793971 ...
5  | 3  1777   571099   198906617    68534828391    23650967140325 ...
6  | 5 11407 13807469 18169793971 23650967140325 30833670159649637 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1-3 are A000045(n-1), A286911, A288031.
Main diagonal is A286913.
Cf. A210662, A099390, A089934, A218354.

T(1,1) corrected by Andrew Howroyd, Jun 04 2017

A051737 Number of 4 X n (0,1)-matrices with no consecutive 1's in any row or column.

Original entry on oeis.org

1, 8, 41, 227, 1234, 6743, 36787, 200798, 1095851, 5980913, 32641916, 178150221, 972290957, 5306478436, 28961194501, 158061670175, 862654025422, 4708111537971, 25695485730239, 140238391149386, 765379824048327, 4177217595760125, 22798023012345528, 124424893212114297

Offset: 0

Stephen G Penrice, Dec 06 1999

Colin Barker, Table of n, a(n) for n = 0..1000
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint.
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math, 11 (1998) 54-60.
Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
Y. Kong, General recurrence theory of ligand binding on a three-dimensional lattice, J. Chem. Phys. Vol. 111 (1999), pp. 4790-4799 (set omega = 1 in Eq. (48)).
Index entries for linear recurrences with constant coefficients, signature (4,9,-5,-4,1).

Row 4 of A089934.

Cf. A051736.

LinearRecurrence[{4, 9, -5, -4, 1}, {1, 8, 41, 227, 1234}, 24] (* Jean-François Alcover, Nov 05 2017 *)

Vec((1+4*x-4*x^3+x^4)/(1-4*x-9*x^2+5*x^3+4*x^4-x^5) + O(x^50)) \\ Michel Marcus, Sep 17 2014

From Yong Kong (ykong(AT)curagen.com), Dec 24 2000: (Start)
a(n) = 4*a(n - 1) + 9*a(n - 2) - 5*a(n - 3) - 4*a(n - 4) + a(n - 5);
G.f.: (1 + 4*x - 4*x^3 + x^4)/(1 - 4*x - 9*x^2 + 5*x^3 + 4*x^4 - x^5). (End)
a(n) = 2*a(n - 1) + 18*a(n - 2) + 9*a(n - 3) - 23*a(n - 4) - 2*a(n - 5) + 6*a(n - 6) - a(n - 7).

More terms from James Sellers, Dec 08 1999

More terms from Michel Marcus, Sep 17 2014

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

Andrew Howroyd, Jan 16 2020

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.

			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.

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.

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

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

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

A089980 Array read by antidiagonals: T(n,m) = number of independent sets in the grid graph P_n X P_m.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 7, 5, 1, 1, 8, 17, 17, 8, 1, 1, 13, 41, 63, 41, 13, 1, 1, 21, 99, 227, 227, 99, 21, 1, 1, 34, 239, 827, 1234, 827, 239, 34, 1, 1, 55, 577, 2999, 6743, 6743, 2999, 577, 55, 1, 1, 89, 1393, 10897, 36787, 55447, 36787, 10897, 1393, 89, 1

Offset: 0

Mitch Harris, Nov 17 2003

This table is indexed starting at 0. The table in A089934 is 1 based.

A181031 is essentially the same array (see the Comments by Steve Butler in A006506). - N. J. A. Sloane, Jan 27 2015

			Square array T(n,m) begins:
  1,  1,  1,   1,    1,     1, ...
  1,  2,  3,   5,    8,    13, ...
  1,  3,  7,  17,   41,    99, ...
  1,  5, 17,  63,  227,   827, ...
  1,  8, 41, 227, 1234,  6743, ...
  1, 13, 99, 827, 6743, 55447, ...

Liang Kai, Antidiagonals n = 0..78, flattened
Kai Liang, Independent Set Enumeration in King Graphs by Tensor Network Contractions, arXiv:2505.12776 [math.CO], 2025. See p. 1.
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 1.

Main entry: A089934.
Main diagonal gives A006506.
Cf. A181031.

A089939 T(i,j) = 1 if F(i) AND F(j) = 0, otherwise 0, where F is A003714 and AND is the bitwise logical-and operation. Table read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1

Offset: 0

Marc LeBrun, Nov 15 2003

Encodes which row/column patterns may be adjacent in 01-matrices where no two 0 elements may be adjacent. Contains many interesting recursive patterns such as Fibonacci-sized blocks of 0's along main diagonal.

			T(3,4) = 0 because F(3) AND F(4) = 4 AND 5 = 1, which is nonzero.

Cf. A003714 (Fibbinary), A005614 (row or column 1).
Cf. A000045, A047999.
Cf. A001333, A051736, A051737, A089934, A089935, A089936, A089937, A089938.

Name clarified by Jon E. Schoenfield, Aug 19 2022

cp's OEIS Frontend

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A051737 Number of 4 X n (0,1)-matrices with no consecutive 1's in any row or column.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A089980 Array read by antidiagonals: T(n,m) = number of independent sets in the grid graph P_n X P_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A089939 T(i,j) = 1 if F(i) AND F(j) = 0, otherwise 0, where F is A003714 and AND is the bitwise logical-and operation. Table read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions