login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #14 Mar 17 2018 04:04:01

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

%T 218,38,7,8,51,405,1649,1649,405,51,8,9,66,724,4192,10130,4192,724,66,

%U 9,10,83,1277,10889,34801,34801,10889,1277,83,10

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

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

%H Andrew Howroyd, <a href="/A291543/b291543.txt">Table of n, a(n) for n = 1..1275</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>

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

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

%e Array begins:

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

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

%e ---|-----------------------------------------------------

%e 1 | 1 2 3 4 5 6 7 8...

%e 2 | 2 6 11 18 27 38 51 66...

%e 3 | 3 11 48 109 218 405 724 1277...

%e 4 | 4 18 109 632 1649 4192 10889 29480...

%e 5 | 5 27 218 1649 10130 34801 116772 402673...

%e 6 | 6 38 405 4192 34801 194292 856225 3804880...

%e 7 | 7 51 724 10889 116772 856225 4730810 24810465...

%e 8 | 8 66 1277 29480 402673 3804880 24810465 145114944...

%e ...

%t T32[n_, k_] := n^k + k^n - Min[n, k]!*StirlingS2[Max[n, k], Min[n, k]];

%t 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 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];

%t Table[T[m - n + 1, n], {m, 1, 10}, {n, 1, m}] // Flatten(* _Jean-François Alcover_, Nov 01 2017, after _Andrew Howroyd_ *)

%o (PARI) \\ here s(n,k) is A008299(n,k) and b(m,n,1) is A290632(m,n).

%o s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );

%o 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));

%o 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) ))}

%o T(m, n) = b(m, n, 1) + p(m, n, 1);

%Y Main diagonal is A291104.

%Y Cf. A008299, A290586, A290632, A290818.

%K nonn,tabl

%O 1,2

%A _Andrew Howroyd_, Aug 25 2017