A290586 Number of irredundant sets in the n X n rook graph.

2, 11, 94, 1185, 20106, 453271, 13169346, 476777153, 20869990066, 1076251513071, 64077661097418, 4337014196039377, 329768528011095642, 27905789218764082151, 2608140451597365915346, 267506385903592339178241, 29943760423790270319833826

Offset

1,1

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Andrew Howroyd, Irredundant Sets in Rook Graphs

Eric Weisstein's World of Mathematics, Irredundant Set

Eric Weisstein's World of Mathematics, Rook Graph

Formula

a(n) = 2*n^n - n! + Sum_{k=0..n-1} Sum_{r=2*k..n-1} binomial(n,k) * binomial(n,r) * k! * A008299(r,k) * c(n-k,n-r) where c(m,n) = Sum_{i=0..m-1} binomial(n,i) * (n^i - n!*stirling2(i, n)). - Andrew Howroyd, Aug 11 2017

Mathematica

s[n_, k_]:=Sum[(-1)^i*Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}];
c[m_, n_, x_]:=Sum[Binomial[m, i] (n^i - n!*StirlingS2[i, n])*x^i, {i, 0, m - 1}];
p[m_, n_, x_]:=Sum[Sum[Binomial[m, k] Binomial[n, r]* k!*s[r, k]*x^r*c[m - k, n - r, x], {r, 2k, n - 1}], {k, 0, m - 1}];
Table[2*n^n - n! + p[n, n, 1], {n, 30}]
(* Indranil Ghosh, Aug 12 2017, after PARI code *)

Prog

(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) );
c(m, n, x)=sum(i=0, m-1, binomial(m, i) * (n^i - n!*stirling(i, n, 2))*x^i);
p(m, n, x)={sum(k=0, m-1, sum(r=2*k, n-1, binomial(m, k) * binomial(n, r) * k! * s(r, k) * x^r * c(m-k, n-r, x) ))}
a(n) = 2*n^n - n! + p(n, n, 1); \\ Andrew Howroyd, Aug 11 2017

Crossrefs

Main diagonal of A290818.

Row sums of A290823.

Cf. A008299, A248744.

Sequence in context: A158837 A236962 A292916 * A098621 A266834 A131407

Adjacent sequences: A290583 A290584 A290585 * A290587 A290588 A290589

Keyword

nonn

Author

Eric W. Weisstein, Aug 07 2017

Extensions

a(4) corrected and a(5) from Andrew Howroyd, Aug 07 2017

Terms a(6) and beyond from Andrew Howroyd, Aug 11 2017

Status

approved