|
%I #20 Oct 12 2017 03:33:30
%S 1,13,397,55933,31450861,67253507293,559182556492477,
%T 18408476382988290493,2416307646576708948065581,
%U 1267404418454077249779938768413,2658301080374793666228695738368407037,22300360304310794054520197736231374212892413
%N Number of connected induced (non-null) subgraphs of the n X n rook graph.
%H Andrew Howroyd, <a href="/A286189/b286189.txt">Table of n, a(n) for n = 1..50</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%F 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 a(n) ~ 2^(n^2). - _Vaclav Kotesovec_, Oct 12 2017
%t {1} ~ Join ~ Table[g = GraphData[{"Rook", {n,n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 2, 4}]
%t (* Second program: *)
%t (* b = A183109, T = A262307 *)
%t b[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
%t 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 a[n_] := Sum[Binomial[n, i]*Binomial[n, j]*T[i, j], {i, 1, n}, {j, 1, n}];
%t Array[a, 12] (* _Jean-François Alcover_, Oct 11 2017, after _Andrew Howroyd_ *)
%o (PARI)
%o G(N)={my(S=matrix(N,N), T=matrix(N,N), U=matrix(N,N));
%o \\ S is A183109, T is A262307, U is mxn variant of this sequence.
%o for(m=1,N,for(n=1,N,
%o S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
%o 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 U[m,n]=sum(i=1,m,sum(j=1,n,binomial(m,i)*binomial(n,j)*T[i,j])) ));U}
%o a(n)=G(n)[n,n]; \\ _Andrew Howroyd_, May 22 2017
%Y Cf. A262307, A183109.
%Y 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 nonn
%O 1,2
%A _Giovanni Resta_, May 04 2017
%E Terms a(7) and beyond from _Andrew Howroyd_, May 22 2017
|
