A360875 -id:A360875 - cp's OEIS frontend

A360873 Array read by antidiagonals: T(m,n) is the number of (non-null) connected induced subgraphs in the rook graph K_m X K_n.

1, 3, 3, 7, 13, 7, 15, 51, 51, 15, 31, 205, 397, 205, 31, 63, 843, 3303, 3303, 843, 63, 127, 3493, 27877, 55933, 27877, 3493, 127, 255, 14451, 233751, 943095, 943095, 233751, 14451, 255, 511, 59485, 1938517, 15678925, 31450861, 15678925, 1938517, 59485, 511

Offset: 1

Andrew Howroyd, Feb 24 2023

			Array begins:
=======================================================
m\n|  1    2      3        4          5           6 ...
---+---------------------------------------------------
1  |  1    3      7       15         31          63 ...
2  |  3   13     51      205        843        3493 ...
3  |  7   51    397     3303      27877      233751 ...
4  | 15  205   3303    55933     943095    15678925 ...
5  | 31  843  27877   943095   31450861  1033355223 ...
6  | 63 3493 233751 15678925 1033355223 67253507293 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals).
Eric Weisstein's World of Mathematics, Rook Graph.
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph.

Main diagonal is A286189.
Rows 1..2 are A000225, A360874.
Cf. A360850, A360851, A360853, A360875.

\\ S is A183109, T is A262307, U is this sequence.
G(M,N=M)={ my(S=matrix(M, N), T=matrix(M, N), U=matrix(M, N));
for(m=1, M, 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
}
{ my(A=G(7)); for(n=1, #A~, print(A[n,])) }

T(m,n) = Sum_{i=1..m} Sum_{j=1..n} binomial(m, i) * binomial(n, j) * A262307(i, j).

T(m,n) = T(n,m).

A289196 Number of connected dominating sets in the n X n rook graph.

Original entry on oeis.org

1, 9, 325, 51465, 30331861, 66273667449, 556170787050565, 18374555799096912585, 2414861959450912233421141, 1267166974391002542218440851129, 2658149210218078451926703769353958085, 22299979556058598891936157095746389850916425

Offset: 1

Eric W. Weisstein, Jun 28 2017

nonn

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

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

Main diagonal of A360875.

Cf. A183109, A262307, A286189, A287065.

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

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

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

Terms a(6) and beyond from Andrew Howroyd, Jul 18 2017

A360876 Number of connected dominating sets in the 2 X n rook graph.

Original entry on oeis.org

3, 9, 39, 177, 783, 3369, 14199, 58977, 242463, 989529, 4017159, 16245777, 65514543, 263652489, 1059392919, 4251920577, 17050729023, 68332056249, 273715645479, 1096024843377, 4387586157903, 17560804984809, 70274600998839, 281192547174177, 1125052618233183

Offset: 1

Andrew Howroyd, Feb 24 2023

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (8,-19,12).

Row 2 of A360875.

Cf. A360874.

LinearRecurrence[{8, -19, 12}, {3, 9, 39}, 30] (* Paolo Xausa, Oct 03 2024 *)

Vec(3*(1 - 5*x + 8*x^2)/((1 - x)*(1 - 3*x)*(1 - 4*x)) + O(x^25))

a(n) = 8*a(n-1) - 19*a(n-2) + 12*a(n-3) for n > 3.

G.f.: 3*x*(1 - 5*x + 8*x^2)/((1 - x)*(1 - 3*x)*(1 - 4*x)).

cp's OEIS Frontend

A360873 Array read by antidiagonals: T(m,n) is the number of (non-null) connected induced subgraphs in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A289196 Number of connected dominating sets in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A360876 Number of connected dominating sets in the 2 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula