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,2

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

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

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

Prog

(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

Crossrefs

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

Sequence in context: A013527 A009010 A171196 * A280553 A162446 A284824

Adjacent sequences: A286186 A286187 A286188 * A286190 A286191 A286192

Keyword

nonn

Author

Giovanni Resta, May 04 2017

Extensions

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

Status

approved