login
A290586
Number of irredundant sets in the n X n rook graph.
5
2, 11, 94, 1185, 20106, 453271, 13169346, 476777153, 20869990066, 1076251513071, 64077661097418, 4337014196039377, 329768528011095642, 27905789218764082151, 2608140451597365915346, 267506385903592339178241, 29943760423790270319833826
OFFSET
1,1
LINKS
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.
Sequence in context: A158837 A236962 A292916 * A098621 A266834 A131407
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