cp's OEIS Frontend

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

%I A291543 #15 Feb 16 2025 08:33:50
%S A291543 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 A291543 218,38,7,8,51,405,1649,1649,405,51,8,9,66,724,4192,10130,4192,724,66,
%U A291543 9,10,83,1277,10889,34801,34801,10889,1277,83,10
%N A291543 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the lattice (rook) graph K_m X K_n.
%C A291543 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 A291543 Andrew Howroyd, <a href="/A291543/b291543.txt">Table of n, a(n) for n = 1..1275</a>
%H A291543 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>
%H A291543 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%F A291543 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 A291543 Array begins:
%e A291543 =========================================================
%e A291543 m\n| 1  2    3     4      5       6        7         8
%e A291543 ---|-----------------------------------------------------
%e A291543 1  | 1  2    3     4      5       6        7         8...
%e A291543 2  | 2  6   11    18     27      38       51        66...
%e A291543 3  | 3 11   48   109    218     405      724      1277...
%e A291543 4  | 4 18  109   632   1649    4192    10889     29480...
%e A291543 5  | 5 27  218  1649  10130   34801   116772    402673...
%e A291543 6  | 6 38  405  4192  34801  194292   856225   3804880...
%e A291543 7  | 7 51  724 10889 116772  856225  4730810  24810465...
%e A291543 8  | 8 66 1277 29480 402673 3804880 24810465 145114944...
%e A291543 ...
%t A291543 T32[n_, k_] := n^k + k^n - Min[n, k]!*StirlingS2[Max[n, k], Min[n, k]];
%t A291543 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 A291543 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 A291543 Table[T[m - n + 1, n], {m, 1, 10}, {n, 1, m}] // Flatten(* _Jean-François Alcover_, Nov 01 2017, after _Andrew Howroyd_ *)
%o A291543 (PARI) \\ here s(n,k) is A008299(n,k) and b(m,n,1) is A290632(m,n).
%o A291543 s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
%o A291543 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 A291543 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 A291543 T(m, n) = b(m, n, 1) + p(m, n, 1);
%Y A291543 Main diagonal is A291104.
%Y A291543 Cf. A008299, A290586, A290632, A290818.
%K A291543 nonn,tabl
%O A291543 1,2
%A A291543 _Andrew Howroyd_, Aug 25 2017