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

1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413

Offset: 1

Author

Giovanni Resta, May 04 2017

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• Eric Weisstein's World of Mathematics, Rook Graph
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Crossrefs

Main diagonal of A360873.

Cf. A262307, A183109.

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).

Programs

Mathematica

{1} ~ Join ~ Table[g = GraphData[{"Rook", {n,n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 2, 4}]
(* Second program: *)
(* b = A183109, T = A262307 *)
b[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
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}];
a[n_] := Sum[Binomial[n, i]*Binomial[n, j]*T[i, j], {i, 1, n}, {j, 1, n}];
Array[a, 12] (* Jean-François Alcover, Oct 11 2017, after Andrew Howroyd *)

PARI

G(N)={my(S=matrix(N,N), T=matrix(N,N), U=matrix(N,N));
\\ S is A183109, T is A262307, U is mxn variant of this sequence.
for(m=1,N,for(n=1,N,
S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
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)));
U[m,n]=sum(i=1,m,sum(j=1,n,binomial(m,i)*binomial(n,j)*T[i,j])) ));U}
a(n)=G(n)[n,n]; \\ Andrew Howroyd, May 22 2017

Formula

a(n) = Sum_{i=1..n} Sum_{j=1..n} binomial(n,i)*binomial(n,j)*A262307(i,j). - Andrew Howroyd, May 22 2017

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 12 2017

Extensions

Terms a(7) and beyond from Andrew Howroyd, May 22 2017