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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A289196 Number of connected dominating sets in the n X n rook graph. 2
1, 9, 325, 51465, 30331861, 66273667449, 556170787050565, 18374555799096912585, 2414861959450912233421141, 1267166974391002542218440851129, 2658149210218078451926703769353958085, 22299979556058598891936157095746389850916425 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

A set of vertices in the n X n rook graph can be represented as a n X n binary matrix. The vertex set will be dominating if either every row contains a 1 or every column contains a 1. - Andrew Howroyd, Jul 18 2017

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..50

Eric Weisstein's World of Mathematics, Connected Dominating Set

Eric Weisstein's World of Mathematics, Rook Graph

FORMULA

a(n) = A262307(n,n) + 2*Sum_{k=1..n-1} binomial(n,k) * A262307(n,k). - Andrew Howroyd, Jul 18 2017

MATHEMATICA

(* b = A183109, T = A262307 *) b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}]; T[_, 1] = T[1, _] = 1; 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_] := T[n, n] + 2*Sum[ Binomial[n, k]*T[n, k], {k, 1, n-1}]; Array[a, 12] (* Jean-Fran├žois Alcover, Oct 02 2017, after Andrew Howroyd *)

PROG

(PARI)

G(N)={S=matrix(N, N); T=matrix(N, N); U=matrix(N, N);

\\ S is A183109, T is A262307, U is m X n 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, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n, j)*T[m, j])-T[m, n] )); U}

a(n)=G(n)[n, n]; \\ Andrew Howroyd, Jul 18 2017

CROSSREFS

Cf. A183109, A262307, A286189, A287065.

Sequence in context: A203763 A041619 A111968 * A266907 A288547 A303208

Adjacent sequences:  A289193 A289194 A289195 * A289197 A289198 A289199

KEYWORD

nonn

AUTHOR

Eric W. Weisstein, Jun 28 2017

EXTENSIONS

Terms a(6) and beyond from Andrew Howroyd, Jul 18 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 February 20 21:07 EST 2019. Contains 320348 sequences. (Running on oeis4.)