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,8

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

Links

Table of n, a(n) for n=0..77.

Eric Weisstein's World of Mathematics, King Graph

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

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

Example

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

Crossrefs

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

Sequence in context: A162741 A340145 A104320 * A340142 A242618 A180264

Adjacent sequences: A350815 A350816 A350817 * A350819 A350820 A350821

Keyword

nonn,tabl

Author

Andrew Howroyd, Jan 17 2022

Status

approved