cp's OEIS Frontend

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

%I A286189 #24 May 22 2025 22:34:29
%S A286189 1,13,397,55933,31450861,67253507293,559182556492477,
%T A286189 18408476382988290493,2416307646576708948065581,
%U A286189 1267404418454077249779938768413,2658301080374793666228695738368407037,22300360304310794054520197736231374212892413
%N A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.
%H A286189 Andrew Howroyd, <a href="/A286189/b286189.txt">Table of n, a(n) for n = 1..50</a>
%H A286189 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%H A286189 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%F A286189 a(n) = Sum_{i=1..n} Sum_{j=1..n} binomial(n,i)*binomial(n,j)*A262307(i,j). - _Andrew Howroyd_, May 22 2017
%F A286189 a(n) ~ 2^(n^2). - _Vaclav Kotesovec_, Oct 12 2017
%t A286189 {1} ~ Join ~ Table[g = GraphData[{"Rook", {n,n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 2, 4}]
%t A286189 (* Second program: *)
%t A286189 (* b = A183109, T = A262307 *)
%t A286189 b[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
%t A286189 T[m_, n_] := T[m, n] = b[m, n] - Sum[T[i, j]*b[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
%t A286189 a[n_] := Sum[Binomial[n, i]*Binomial[n, j]*T[i, j], {i, 1, n}, {j, 1, n}];
%t A286189 Array[a, 12] (* _Jean-François Alcover_, Oct 11 2017, after _Andrew Howroyd_ *)
%o A286189 (PARI)
%o A286189 G(N)={my(S=matrix(N,N), T=matrix(N,N), U=matrix(N,N));
%o A286189 \\ S is A183109, T is A262307, U is mxn variant of this sequence.
%o A286189 for(m=1,N,for(n=1,N,
%o A286189 S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
%o A286189 T[m,n]=S[m,n]-sum(i=1, m-1, sum(j=1, n-1, T[i,j]*S[m-i,n-j]*binomial(m-1,i-1)*binomial(n,j)));
%o A286189 U[m,n]=sum(i=1,m,sum(j=1,n,binomial(m,i)*binomial(n,j)*T[i,j])) ));U}
%o A286189 a(n)=G(n)[n,n]; \\ _Andrew Howroyd_, May 22 2017
%Y A286189 Main diagonal of A360873.
%Y A286189 Cf. A262307, A183109.
%Y A286189 Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A285765 (queen).
%K A286189 nonn
%O A286189 1,2
%A A286189 _Giovanni Resta_, May 04 2017
%E A286189 Terms a(7) and beyond from _Andrew Howroyd_, May 22 2017