A384120 Array read by antidiagonals: T(n,m) is the number of cliques in the n X m rook graph K_n X K_m.

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 9, 8, 1, 1, 16, 18, 18, 16, 1, 1, 32, 35, 34, 35, 32, 1, 1, 64, 68, 62, 62, 68, 64, 1, 1, 128, 133, 114, 105, 114, 133, 128, 1, 1, 256, 262, 214, 180, 180, 214, 262, 256, 1, 1, 512, 519, 410, 319, 286, 319, 410, 519, 512, 1

Offset

0,5

Comments

Also the number of independent vertex sets in the n X m rook complement graph.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Eric Weisstein's World of Mathematics, Clique.

Eric Weisstein's World of Mathematics, Rook Graph.

Formula

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

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

Example

Array begins:
=================================================
n\m | 0   1   2   3    4    5    6    7    8 ...
----+-------------------------------------------
  0 | 1   1   1   1    1    1    1    1    1 ...
  1 | 1   2   4   8   16   32   64  128  256 ...
  2 | 1   4   9  18   35   68  133  262  519 ...
  3 | 1   8  18  34   62  114  214  410  798 ...
  4 | 1  16  35  62  105  180  319  586 1109 ...
  5 | 1  32  68 114  180  286  472  818 1484 ...
  6 | 1  64 133 214  319  472  721 1162 1987 ...
  7 | 1 128 262 410  586  818 1162 1730 2746 ...
  8 | 1 256 519 798 1109 1484 1987 2746 4017 ...
  ...

Prog

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

Crossrefs

Main diagonal is A288958.

Columns 0..3 are A000012, A000079, A083706, A250770(n-1).

Cf. A384121.

Sequence in context: A056588 A126770 A202979 * A384124 A306326 A156006

Adjacent sequences: A384117 A384118 A384119 * A384121 A384122 A384123

Keyword

nonn,tabl,easy

Author

Andrew Howroyd, May 20 2025

Status

approved