A350818 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the m X n king graph.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 12, 1, 12, 1, 1, 1, 4, 8, 9, 9, 8, 4, 1, 1, 1, 32, 1, 79, 1, 32, 1, 1, 1, 5, 16, 16, 27, 27, 16, 16, 5, 1, 1, 1, 80, 1, 408, 1, 408, 1, 80, 1, 1, 1, 6, 32, 25, 81, 64, 64, 81, 25, 32, 6, 1

Offset: 0

Author

Andrew Howroyd, Jan 17 2022

Keywords

• nonn
• tabl

Comments

The maximum size of an independent set is the independence number which in the case of an m X n king graph is given by ceiling(m/2)*ceiling(n/2).

Examples

			Table begins:
=============================================
m\n | 0 1  2  3    4   5     6   7      8
----+----------------------------------------
  0 | 1 1  1  1    1   1     1   1      1 ...
  1 | 1 1  2  1    3   1     4   1      5 ...
  2 | 1 2  4  4   12   8    32  16     80 ...
  3 | 1 1  4  1    9   1    16   1     25 ...
  4 | 1 3 12  9   79  27   408  81   1847 ...
  5 | 1 1  8  1   27   1    64   1    125 ...
  6 | 1 4 32 16  408  64  3600 256  26040 ...
  7 | 1 1 16  1   81   1   256   1    625 ...
  8 | 1 5 80 25 1847 125 26040 625 281571 ...
  ...
		

Links

• Eric Weisstein's World of Mathematics, King Graph
• Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Crossrefs

Cf. A018807, A245013, A332347, A350815, A350819.

Formula

T(m,n) = T(n,m).

T(2*m+1, 2*n+1) = 1.

T(2*m, 2*n+1) = (1+m)^(1+n).

T(2*m, 2*n) = A350819(m, n).