login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 22 11:34 EDT 2019. Contains 326176 sequences. (Running on oeis4.)