|
| |
|
|
A286189
|
|
Number of connected induced (non-null) subgraphs of the n X n rook graph.
|
|
18
|
|
|
|
1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
| |
|
|
