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

%I #11 Aug 28 2017 09:21:21

%S 1,6,48,632,10130,194292,4730810,145114944,5529662802,256094790500,

%T 14038667879522,890349688082736,64160617557387338,5183023418382933060,

%U 464623151635449639450,45857185726197195813632,4951604249874284663582498,581839639424819461006405956

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

%H Andrew Howroyd, <a href="/A291104/b291104.txt">Table of n, a(n) for n = 1..100</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>

%F 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

%t (* Start *)

%t s[n_, k_] := Sum[(-1)^i Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}]

%t 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}]

%t a[n_] := 2 n^n - n! + p[n, n, 1]

%t Array[a, 20]

%t (* End *)

%o (PARI) \\ here s(n, k) is A008299, 2*n^n - n! is A248744.

%o s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );

%o 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) ))}

%o a(n) = 2*n^n - n! + p(n,n,1); \\ _Andrew Howroyd_, Aug 25 2017

%Y Main diagonal of A291543.

%Y Cf. A008299, A248744, A290586.

%K nonn

%O 1,2

%A _Eric W. Weisstein_, Aug 17 2017

%E Terms a(5) and beyond from _Andrew Howroyd_, Aug 25 2017