cp's OEIS Frontend

A290586 Number of irredundant sets in the n X n rook graph.

%I A290586 #22 Feb 16 2025 08:33:49
%S A290586 2,11,94,1185,20106,453271,13169346,476777153,20869990066,
%T A290586 1076251513071,64077661097418,4337014196039377,329768528011095642,
%U A290586 27905789218764082151,2608140451597365915346,267506385903592339178241,29943760423790270319833826
%N A290586 Number of irredundant sets in the n X n rook graph.
%H A290586 Andrew Howroyd, <a href="/A290586/b290586.txt">Table of n, a(n) for n = 1..100</a>
%H A290586 Andrew Howroyd, <a href="/A290586/a290586.txt">Irredundant Sets in Rook Graphs</a>
%H A290586 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IrredundantSet.html">Irredundant Set</a>
%H A290586 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%F A290586 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
%t A290586 s[n_, k_]:=Sum[(-1)^i*Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}];
%t A290586 c[m_, n_, x_]:=Sum[Binomial[m, i] (n^i - n!*StirlingS2[i, n])*x^i, {i, 0, m - 1}];
%t A290586 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}];
%t A290586 Table[2*n^n - n! + p[n, n, 1], {n, 30}]
%t A290586 (* _Indranil Ghosh_, Aug 12 2017, after PARI code *)
%o A290586 (PARI) \\ here s(n,k) is A008299, 2*n^n - n! is A248744.
%o A290586 s(n,k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
%o A290586 c(m,n,x)=sum(i=0, m-1, binomial(m, i) * (n^i - n!*stirling(i, n, 2))*x^i);
%o A290586 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) ))}
%o A290586 a(n) = 2*n^n - n! + p(n,n,1); \\ _Andrew Howroyd_, Aug 11 2017
%Y A290586 Main diagonal of A290818.
%Y A290586 Row sums of A290823.
%Y A290586 Cf. A008299, A248744.
%K A290586 nonn
%O A290586 1,1
%A A290586 _Eric W. Weisstein_, Aug 07 2017
%E A290586 a(4) corrected and a(5) from _Andrew Howroyd_, Aug 07 2017
%E A290586 Terms a(6) and beyond from _Andrew Howroyd_, Aug 11 2017