A291104 Number of maximal irredundant sets in the n X n rook graph.

1, 6, 48, 632, 10130, 194292, 4730810, 145114944, 5529662802, 256094790500, 14038667879522, 890349688082736, 64160617557387338, 5183023418382933060, 464623151635449639450, 45857185726197195813632, 4951604249874284663582498, 581839639424819461006405956

Offset: 1

Author

Eric W. Weisstein, Aug 17 2017

Keywords

• nonn

Links

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

Crossrefs

Main diagonal of A291543.

Cf. A008299, A248744, A290586.

Programs

Mathematica

(* Start *)
s[n_, k_] := Sum[(-1)^i Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}]
p[m_, n_, x_] := Sum[Binomial[m, k] Binomial[n, j] k! s[n - j, k - 1] j! StirlingS2[m - k, j - 1] x^(m + n - j - k), {k, 2, m - 2}, {j, 2, m - k}]
a[n_] := 2 n^n - n! + p[n, n, 1]
Array[a, 20]
(* End *)

PARI

\\ here s(n, k) is A008299, 2*n^n - n! is A248744.
s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 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) ))}
a(n) = 2*n^n - n! + p(n,n,1); \\ Andrew Howroyd, Aug 25 2017

Formula

a(n) = 2*n^n - n! + Sum_{k=2..n-2} Sum_{j=2..n-k} binomial(n,k) * binomial(n,j) * k! * A008299(n-j,k-1) * j! * stirling2(n-k,j-1). - Andrew Howroyd, Aug 25 2017

Extensions

Terms a(5) and beyond from Andrew Howroyd, Aug 25 2017