A286189 -id:A286189 - cp's OEIS frontend

A285765 Number of connected induced (non-null) subgraphs of the n X n queen graph.

1, 15, 495, 64815, 33478163, 68694593248

Offset: 1

Giovanni Resta, May 04 2017

Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

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), A286189 (rook).

Table[g = GraphData[{"Queen", {n, n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 4}]

A286186 Number of connected induced (non-null) subgraphs of the friendship graph with 2n+1 nodes.

Original entry on oeis.org

7, 22, 73, 268, 1039, 4114, 16405, 65560, 262171, 1048606, 4194337, 16777252, 67108903, 268435498, 1073741869, 4294967344, 17179869235, 68719476790, 274877907001, 1099511627836, 4398046511167, 17592186044482, 70368744177733, 281474976710728, 1125899906842699

Offset: 1

Giovanni Resta, May 04 2017

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Dutch Windmill Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Friendship graph
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

Table[4^n + 3 n, {n, 30}]
LinearRecurrence[{6,-9,4},{7,22,73},40] (* Harvey P. Dale, May 25 2019 *)

Vec(x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 21 2017

a(n) = 4^n + 3*n.
From Colin Barker, May 21 2017: (Start)
G.f.: x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3. (End)
E.g.f.: exp(x)*(exp(3*x) + 3*x) - 1. - Stefano Spezia, Aug 25 2022

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 19, 19, 1, 1, 65, 205, 65, 1, 1, 211, 1795, 1795, 211, 1, 1, 665, 14221, 36317, 14221, 665, 1, 1, 2059, 106819, 636331, 636331, 106819, 2059, 1, 1, 6305, 778765, 10365005, 23679901, 10365005, 778765, 6305, 1

Offset: 1

N. J. A. Sloane, Oct 04 2015

Two 1's are connected if they are in the same row or column. The requirement is for them to form a single connected set.
The number of m X n binary matrices with no zero rows or columns is given by A183109(m, n). If there are multiple components (not connected) then they cannot share either rows or columns. For i < n and j < m there are T(i,j) ways of creating an i X j component that occupies the first row. Its remaining i-1 rows may be on any of the remaining m-1 rows with its j columns on any of the n columns. The m-i rows and n-j columns not used by this component can be any matrix with no zero rows or columns.
T(m,n) is also the number of bipartite connected labeled graphs with parts of size m and n. (See A005333, A227322.)
This is the array a(m,n) in Kreweras (1969). Kreweras describes this as a symmetric triangle read by rows, giving numbers of connected relations.
The companion array b(m,n) (and the first few of its diagonals) in Kreweras (1969) should also be added to the OEIS if they are not already present.

			Table starts:
==========================================================================
m\n| 1    2      3         4           5             6               7
---|----------------------------------------------------------------------
1  | 1    1      1         1           1             1               1 ...
2  | 1    5     19        65         211           665            2059 ...
3  | 1   19    205      1795       14221        106819          778765 ...
4  | 1   65   1795     36317      636331      10365005       162470155 ...
5  | 1  211  14221    636331    23679901     805351531     26175881341 ...
6  | 1  665 106819  10365005   805351531   56294206205   3735873535339 ...
7  | 1 2059 778765 162470155 26175881341 3735873535339 502757743028605 ...
...
As a triangle, this begins:
  1;
  1,    1;
  1,    5,      1;
  1,   19,     19,      1;
  1,   65,    205,     65,      1;
  1,  211,   1795,   1795,    211,      1;
  1,  665,  14221,  36317,  14221,    665,    1;
  1, 2059, 106819, 636331, 636331, 106819, 2059, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..780
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.

Essentially same table as triangle A227322 (where the antidiagonals only go halfway).
Main diagonal is A005333.
Initial diagonals give A001047, A002501, A002502.
Cf. A226658, A123260, A286189, A183109, A048291, A287274.

A183109[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m-j) - 1)^n, {j, 0, m}];
T[m_, n_] := A183109[m, n] - Sum[T[i, j]*A183109[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
Table[T[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

G(N)={my(S=matrix(N,N), T=matrix(N,N));
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)));
));T}
G(7) \\ Andrew Howroyd, May 22 2017

T(m,n) = A183109(m,n) - Sum_{i=1..m-1} Sum_{j=1..n-1} T(i,j)*A183109(m-i, n-j)*binomial(m-1,i-1)*binomial(n,j). - Andrew Howroyd, May 22 2017

Revised by N. J. A. Sloane, May 26 2017, to incorporate material from Andrew Howroyd's May 22 2017 submission (formerly A287297), which was essentially identical to this, although giving an alternative description and more information.

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.

Original entry on oeis.org

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).

A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

Original entry on oeis.org

1, 6, 37, 750, 459829, 210067308558, 44127887746326310604917, 1947270476915296449559791701269341583074001038

Offset: 0

Giovanni Resta, May 05 2017

A perfect (sometimes called complete) binary tree of height k has 2^(k+1)-1 nodes.

a(8) has 91 digits and thus it is not reported.

Alois P. Heinz, Table of n, a(n) for n = 0..11
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Types of binary trees

Cf. A003095, A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

a[1]=b[1]=1; b[n_] := b[n] = 1 + b[n - 1]^2; a[n_] := a[n] = b[n]^2 + 2 a[n - 1]; Array[a, 8]

Let b(0)=1 and b(n) = 1+b(n-1)^2. Then, a(0)=1 and a(n) = b(n)^2 + 2*a(n-1). Note that b(n) = A003095(n+1).

A286191 a(n) = (2^n-1)^2 + 2*n.

Original entry on oeis.org

3, 13, 55, 233, 971, 3981, 16143, 65041, 261139, 1046549, 4190231, 16769049, 67092507, 268402717, 1073676319, 4294836257, 17179607075, 68718952485, 274876858407, 1099509530665, 4398042316843, 17592177655853, 70368727400495, 281474943156273, 1125899839733811

Offset: 1

Giovanni Resta, May 05 2017

Number of connected induced (non-null) subgraphs of the complete bipartite graph K(n,n).

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

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), A286189 (rook), A285765 (queen).

a[n_] := (2^n-1)^2 + 2*n; Array[a, 30]
Table[(2^n - 1)^2 + 2 n, {n, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
LinearRecurrence[{8, -21, 22, -8}, {3, 13, 55, 233}, 20] (* Eric W. Weisstein, Aug 09 2017 *)
CoefficientList[Series[(3 - 11 x + 14 x^2)/((-1 + x)^2 (1 - 6 x + 8 x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 09 2017 *)

Vec(x*(3 - 11*x + 14*x^2) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 30 2017

a(n) = (2^n-1)^2 + 2*n.
From Colin Barker, May 30 2017: (Start)
G.f.: x*(3 - 11*x + 14*x^2) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)).
a(n) = 8*a(n-1) - 21*a(n-2) + 22*a(n-3) - 8*a(n-4) for n>4.
(End)

Name changed to the formula by Eric W. Weisstein, Aug 09 2017

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

A360852 Number of induced paths in the n X n rook graph.

Original entry on oeis.org

0, 8, 126, 2208, 55700, 2006280, 98309778, 6291829376, 509638185288, 50963818537800, 6166622043087110, 887993574204562848, 150070914040571147676, 29413899151951944980168, 6618127309189187620585050, 1694240591152432030869834240, 489635530843052856921382173968

Offset: 1

Andrew Howroyd, Feb 24 2023

nonn

Paths of length zero are not counted here.

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Rook Graph.
Wikipedia, Induced path.

Main diagonal of A360851.

Cf. A000290, A286189 (induced connected subgraphs), A288035, A288967.

a(n) = {sum(k=0, n-1, n!^2*(1 + k)/(k!^2)) - n^2}

a(n) = -n^2 + n!^2 * Sum_{k=0..n-1} (1 + k)/(k!^2).

a(n) = A288035(n) - n^2 = A288035(n) - A000290(n).

A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with n nodes.

Original entry on oeis.org

1, 3, 6, 10, 17, 24, 37, 51, 78, 110, 173, 229, 340, 477, 750, 1024, 1571, 2253, 3616, 5024, 7839, 11356, 18389, 25173, 38740, 55697, 89610, 124870, 195389, 283536, 459829, 636123, 988710, 1429442, 2310905, 3227617, 5061040, 7352817, 11936370, 16526444

Offset: 1

Giovanni Resta, May 05 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..5651 (first 255 terms from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Types of binary trees

Cf. A285934, A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

Join[{1}, Table[g=KaryTree[n]; -1 + ParallelSum[Boole@ConnectedGraphQ@Subgraph[g, s], {s, Subsets@Range[n]}], {n, 2, 16}]]
(* Second program: *)
l[n_] := With[{h = 2^Floor[Log[2, n]]}, Min[h - 1, n - h/2]];
b[n_] := b[n] = 1 + If[n <= 1, n, b[l[n]]*b[n - 1 - l[n]]];
a[n_] := a[n] = If[n <= 1, n, b[n] - 1 + a[l[n]] + a[n - 1 - l[n]]];
Array[a, 40] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

l(n)={my(h=2^floor(log(n)/log(2))); min(h-1,n-h/2)}
b(n)=1+if(n<=1,n,b(l(n))*b(n-1-l(n)));
a(n)=if(n<=1,n,b(n)-1 + a(l(n)) + a(n-1-l(n))); \\ Andrew Howroyd, May 22 2017

a(2^k-1) = A285934(k-1).

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

A362575 Number of vertex cuts in the n X n rook graph.

Original entry on oeis.org

0, 2, 114, 9602, 2103570, 1465969442, 3767396928834, 38267690721261122, 1543992652549401346770, 246181774152151716764436962, 154911195038079578918382192282114, 384894219829087015520536416987293088002, 3779926606713983438336679626484814602924257490

Offset: 1

Eric W. Weisstein, Apr 25 2023

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 Cut

Cf. A286189, A362576.

a(n) = 2^(n^2) - 1 - A286189(n). - Andrew Howroyd, Apr 30 2023

Terms a(6) and beyond from Andrew Howroyd, Apr 30 2023

cp's OEIS Frontend

A285765 Number of connected induced (non-null) subgraphs of the n X n queen graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A286186 Number of connected induced (non-null) subgraphs of the friendship graph with 2n+1 nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A286191 a(n) = (2^n-1)^2 + 2*n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A360852 Number of induced paths in the n X n rook graph.

Views

Author

Keywords