A360873 -id:A360873 - cp's OEIS frontend

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413

Offset: 1

Giovanni Resta, May 04 2017

nonn

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

Main diagonal of A360873.
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).

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

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

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

Terms a(7) and beyond from Andrew Howroyd, May 22 2017

A360875 Array read by antidiagonals: T(m,n) is the number of connected dominating sets in the rook graph K_m X K_n.

Original entry on oeis.org

1, 3, 3, 7, 9, 7, 15, 39, 39, 15, 31, 177, 325, 177, 31, 63, 783, 2931, 2931, 783, 63, 127, 3369, 26077, 51465, 26077, 3369, 127, 255, 14199, 225459, 894675, 894675, 225459, 14199, 255, 511, 58977, 1901725, 15195897, 30331861, 15195897, 1901725, 58977, 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    9     39      177        783        3369 ...
3  |  7   39    325     2931      26077      225459 ...
4  | 15  177   2931    51465     894675    15195897 ...
5  | 31  783  26077   894675   30331861  1010163363 ...
6  | 63 3369 225459 15195897 1010163363 66273667449 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals).
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A289196.
Rows 1..2 are A000225, A360876.
Cf. A287274, A360873.

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

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

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

A360874 Number of (non-null) connected induced subgraphs in the 2 X n rook graph.

Original entry on oeis.org

3, 13, 51, 205, 843, 3493, 14451, 59485, 243483, 991573, 4021251, 16253965, 65530923, 263685253, 1059458451, 4252051645, 17050991163, 68332580533, 273716694051, 1096026940525, 4387590352203, 17560813373413, 70274617776051, 281192580728605, 1125052685342043

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 (10,-35,50,-24).

Row 2 of A360873.

Cf. A360876.

LinearRecurrence[{10, -35, 50, -24}, {3, 13, 51, 205}, 30] (* Paolo Xausa, Oct 03 2024 *)

Vec((3 - 17*x + 26*x^2)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)) + O(x^25))

a(n) = 10*a(n-1) - 35*a(n-2) + 50*a(n-3) - 24*a(n-4) for n > 4.

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

A378935 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the rook graph K_m X K_n.

Original entry on oeis.org

0, 1, 1, 3, 6, 3, 7, 22, 22, 7, 15, 84, 150, 84, 15, 31, 346, 1276, 1276, 346, 31, 63, 1476, 11538, 23214, 11538, 1476, 63, 127, 6322, 102772, 418912, 418912, 102772, 6322, 127, 255, 26844, 890130, 7290534, 14673870, 7290534, 890130, 26844, 255, 511, 112666, 7525876, 123174016, 496484776, 496484776, 123174016, 7525876, 112666, 511

Offset: 1

Andrew Howroyd, Dec 12 2024

			Array begins:
======================================================
m\n |  1    2      3       4         5           6 ...
----+-------------------------------------------------
  1 |  0    1      3       7        15          31 ...
  2 |  1    6     22      84       346        1476 ...
  3 |  3   22    150    1276     11538      102772 ...
  4 |  7   84   1276   23214    418912     7290534 ...
  5 | 15  346  11538  418912  14673870   496484776 ...
  6 | 31 1476 102772 7290534 496484776 32893769886 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
Eric Weisstein's World of Mathematics, Minimal Edge Cut.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A378936.
Rows 1..2 are A000225(n-1), A378937.
Cf. A143088, A360873, A378932.

\\ Needs G from A360873.
T(M,N=M) = {G(M,N) + matrix(M,N,m,n, (2^(m-1) - 1)*(2^(n-1) - 1) - 2^(m*n-1))}
{ my(A=T(7)); for(n=1, #A~, print(A[n,])) }

T(m,n) = A360873(m,n) + (2^(m-1) - 1)*(2^(n-1) - 1) - 2^(m*n-1).

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

cp's OEIS Frontend

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A360875 Array read by antidiagonals: T(m,n) is the number of connected dominating sets in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A360874 Number of (non-null) connected induced subgraphs in the 2 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378935 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula