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
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
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);
Comments