login
A286189
Number of connected induced (non-null) subgraphs of the n X n rook graph.
21
1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413
OFFSET
1,2
LINKS
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. 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
KEYWORD
nonn
AUTHOR
Giovanni Resta, May 04 2017
EXTENSIONS
Terms a(7) and beyond from Andrew Howroyd, May 22 2017
STATUS
approved