login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 23 11:24 EDT 2019. Contains 326222 sequences. (Running on oeis4.)