A286182 -id:A286182 - cp's OEIS frontend

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

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

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

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

A286985 Number of connected dominating sets in the n-prism graph.

Original entry on oeis.org

7, 7, 39, 115, 343, 967, 2663, 7203, 19239, 50887, 133543, 348179, 902775, 2329607, 5986535, 15327555, 39115847, 99532423, 252601127, 639548595, 1615746455, 4073951559, 10253517671, 25763632995, 64635943783, 161928486727, 405134009511, 1012371656275

Offset: 1

Eric W. Weisstein, May 17 2017

nonn

Sequence extrapolated to a(1) and a(2) using recurrence. - Andrew Howroyd, Sep 04 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (6, -11, 4, 5, -2, -1).

Cf. A284702, A286182.

Rest @ CoefficientList[Series[x (7 - 35 x + 74 x^2 - 70 x^3 + 19 x^4 - 3 x^5)/((1 - x)^2*(1 - 2 x - x^2)^2), {x, 0, 28}], x] (* Michael De Vlieger, Sep 04 2017 *)
Table[LucasL[n, 2] + 2 n (3 Fibonacci[n - 2, 2] + Fibonacci[n - 1, 2] - 1) + 1, {n, 20}] (* Eric W. Weisstein, Sep 08 2017 *)
LinearRecurrence[{6, -11, 4, 5, -2, -1}, {7, 7, 39, 115, 343, 967}, 20] (* Eric W. Weisstein, Sep 08 2017 *)

Vec((7 - 35*x + 74*x^2 - 70*x^3 + 19*x^4 - 3*x^5)/((1 - x)^2*(1 - 2*x - x^2)^2) + O(x^30))

From Andrew Howroyd, Sep 04 2017: (Start)
a(n) = 6*a(n-1) - 11*a(n-2) + 4*a(n-3) + 5*a(n-4) - 2*a(n-5) - a(n-6) for n > 6.
G.f.: x*(7 - 35*x + 74*x^2 - 70*x^3 + 19*x^4 - 3*x^5)/((1 - x)^2*(1 - 2*x - x^2)^2).
(End)

a(1)-a(2) and terms a(14) and beyond from Andrew Howroyd, Sep 04 2017

A356830 Number of vertex cuts in the n-prism graph.

Original entry on oeis.org

0, 2, 12, 88, 520, 2654, 12376, 54612, 232788, 970538, 3988644, 16239088, 65709280, 264814166, 1064414128, 4271035692, 17118683052, 68563527650, 274481537148, 1098506723080, 4395504614584, 17585769696206, 70352578566664, 281434319454084, 1125797816327940

Offset: 1

Eric W. Weisstein, Aug 30 2022

nonn

Sequence extended to n = 1 using formula.

Eric Weisstein's World of Mathematics, Prism Graph
Eric Weisstein's World of Mathematics, Vertex Cut
Index entries for linear recurrences with constant coefficients, signature (10,-35,48,-11,-22,7,4).

Cf. A286182, A000129, A002203.

Table[4^n + 3 n - 3 n Fibonacci[n, 2] - LucasL[n, 2] - 2, {n, 20}]
LinearRecurrence[{10, -35, 48, -11, -22, 7, 4}, {0, 2, 12, 88, 520, 2654, 12376}, 20]
CoefficientList[Series[2 x (-1 + 4 x - 19 x^2 + 18 x^3 + 10 x^4 + 6 x^5)/((-1 + x)^2 (-1 + 4 x) (-1 + 2 x + x^2)^2), {x, 0, 20}], x]

a(n) = 2^(2*n) - A286182(n) - 1. - Pontus von Brömssen, Aug 30 2022
From Eric W. Weisstein, Aug 31 2022: (Start)
a(n) = 4^n + 3*n - 3*n*Fibonacci(n, 2) - Lucas(n, 2), where Fibonacci(n, 2) = A000129(n) and Lucas(n, 2) = A002203(n).
a(n) = 10*a(n-1) - 35*a(n-2) + 48*a(n-3) - 11*a(n-4) - 22*a(n-5) + 7*a(n-6) + 4*a(n-7).
G.f.: 2*x^2*(-1 + 4*x - 19*x^2 + 18*x^3 + 10*x^4 + 6*x^5)/((-1 + x)^2*(-1 + 4*x)*(-1 + 2*x + x^2)^2). (End)

More terms from Pontus von Brömssen, Aug 30 2022

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A286985 Number of connected dominating sets in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A356830 Number of vertex cuts in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions