login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291104 Number of maximal irredundant sets in the n X n rook graph. 2
1, 6, 48, 632, 10130, 194292, 4730810, 145114944, 5529662802, 256094790500, 14038667879522, 890349688082736, 64160617557387338, 5183023418382933060, 464623151635449639450, 45857185726197195813632, 4951604249874284663582498, 581839639424819461006405956 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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

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 *)

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

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

CROSSREFS

Main diagonal of A291543.

Cf. A008299, A248744, A290586.

Sequence in context: A113388 A113393 A138426 * A108092 A052744 A267620

Adjacent sequences:  A291101 A291102 A291103 * A291105 A291106 A291107

KEYWORD

nonn

AUTHOR

Eric W. Weisstein, Aug 17 2017

EXTENSIONS

Terms a(5) and beyond from Andrew Howroyd, Aug 25 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 October 27 20:04 EDT 2021. Contains 348289 sequences. (Running on oeis4.)