A291543 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the lattice (rook) graph K_m X K_n.

1, 2, 2, 3, 6, 3, 4, 11, 11, 4, 5, 18, 48, 18, 5, 6, 27, 109, 109, 27, 6, 7, 38, 218, 632, 218, 38, 7, 8, 51, 405, 1649, 1649, 405, 51, 8, 9, 66, 724, 4192, 10130, 4192, 724, 66, 9, 10, 83, 1277, 10889, 34801, 34801, 10889, 1277, 83, 10

Offset: 1

Author

Andrew Howroyd, Aug 25 2017

Keywords

• nonn
• tabl

Comments

Maximal irredundant sets can be either dominating or not. The dominating maximal irredundant sets are the minimal dominating sets (A290632). The non-dominating maximal irredundant sets are those irredundant sets that have exactly one empty row and one empty column and at least one row and one column with more than one element. See note in A290586 for some additional details.

Examples

			Array begins:
=========================================================
m\n| 1  2    3     4      5       6        7         8
---|-----------------------------------------------------
1  | 1  2    3     4      5       6        7         8...
2  | 2  6   11    18     27      38       51        66...
3  | 3 11   48   109    218     405      724      1277...
4  | 4 18  109   632   1649    4192    10889     29480...
5  | 5 27  218  1649  10130   34801   116772    402673...
6  | 6 38  405  4192  34801  194292   856225   3804880...
7  | 7 51  724 10889 116772  856225  4730810  24810465...
8  | 8 66 1277 29480 402673 3804880 24810465 145114944...
...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Eric Weisstein's World of Mathematics, Maximal Irredundant Set
• Eric Weisstein's World of Mathematics, Rook Graph

Crossrefs

Main diagonal is A291104.

Cf. A008299, A290586, A290632, A290818.

Programs

Mathematica

T32[n_, k_] := n^k + k^n - Min[n, k]!*StirlingS2[Max[n, k], Min[n, k]];
T99[n_, k_] := Sum[(-1)^i*Binomial[n, i]*Sum[(-1)^j*((k - i - j)^(n - i)/(j!*(k - i - j)!)), {j, 0, k - i}], {i, 0, k}];
T[m_, n_] /; n >= m := T32[m, n] + Sum[Sum[Binomial[m, k]*Binomial[n, j]*k!*T99[n - j, k - 1]*j!*StirlingS2[m - k, j - 1], {j, 2, m - k}], {k, 2, m - 2}]; T[m_, n_] /; n < m := T[n, m];
Table[T[m - n + 1, n], {m, 1, 10}, {n, 1, m}] // Flatten(* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

PARI

\\ here s(n,k) is A008299(n,k) and b(m,n,1) is A290632(m,n).
s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
b(m, n, x) = m^n*x^n + n^m*x^m - if(n<=m, n!*x^m*stirling(m, n, 2), m!*x^n*stirling(n, m, 2));
p(m, n, x)={sum(k=2, m-2, sum(j=2, m-k, binomial(m, k) * binomial(n, j) * k! * s(n-j, k-1) * j! * stirling(m-k, j-1, 2) * x^(m+n-j-k) ))}
T(m, n) = b(m, n, 1) + p(m, n, 1);

Formula

T(m,n) = A290632(m, n) + Sum_{k=2..m-2} Sum_{j=2..m-k} binomial(m,k) * binomial(n,j) * k! * A008299(n-j,k-1) * j! * stirling2(m-k,j-1).