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

%I #9 Jan 17 2022 20:06:06

%S 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,

%T 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,

%U 408,1,80,1,1,1,6,32,25,81,64,64,81,25,32,6,1

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentVertexSet.html">Maximum Independent Vertex Set</a>

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

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

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

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

%e Table begins:

%e =============================================

%e m\n | 0 1 2 3 4 5 6 7 8

%e ----+----------------------------------------

%e 0 | 1 1 1 1 1 1 1 1 1 ...

%e 1 | 1 1 2 1 3 1 4 1 5 ...

%e 2 | 1 2 4 4 12 8 32 16 80 ...

%e 3 | 1 1 4 1 9 1 16 1 25 ...

%e 4 | 1 3 12 9 79 27 408 81 1847 ...

%e 5 | 1 1 8 1 27 1 64 1 125 ...

%e 6 | 1 4 32 16 408 64 3600 256 26040 ...

%e 7 | 1 1 16 1 81 1 256 1 625 ...

%e 8 | 1 5 80 25 1847 125 26040 625 281571 ...

%e ...

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

%K nonn,tabl

%O 0,8

%A _Andrew Howroyd_, Jan 17 2022