cp's OEIS Frontend

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

%I A291104 #12 Feb 16 2025 08:33:50
%S A291104 1,6,48,632,10130,194292,4730810,145114944,5529662802,256094790500,
%T A291104 14038667879522,890349688082736,64160617557387338,5183023418382933060,
%U A291104 464623151635449639450,45857185726197195813632,4951604249874284663582498,581839639424819461006405956
%N A291104 Number of maximal irredundant sets in the n X n rook graph.
%H A291104 Andrew Howroyd, <a href="/A291104/b291104.txt">Table of n, a(n) for n = 1..100</a>
%H A291104 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>
%H A291104 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%F A291104 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 A291104 (* Start *)
%t A291104 s[n_, k_] := Sum[(-1)^i Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}]
%t A291104 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 A291104 a[n_] := 2 n^n - n! + p[n, n, 1]
%t A291104 Array[a, 20]
%t A291104 (* End *)
%o A291104 (PARI) \\ here s(n, k) is A008299, 2*n^n - n! is A248744.
%o A291104 s(n, k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
%o A291104 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 A291104 a(n) = 2*n^n - n! + p(n,n,1); \\ _Andrew Howroyd_, Aug 25 2017
%Y A291104 Main diagonal of A291543.
%Y A291104 Cf. A008299, A248744, A290586.
%K A291104 nonn
%O A291104 1,2
%A A291104 _Eric W. Weisstein_, Aug 17 2017
%E A291104 Terms a(5) and beyond from _Andrew Howroyd_, Aug 25 2017