A292300 -id:A292300 - cp's OEIS frontend

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

1, 7, 60, 968, 31737, 2069963, 267270032, 68629753640, 35171000942697, 36024807353574279, 73784587576805254652, 302228602363365451957792, 2475873310144021668263093201, 40564787336902311168400640561083, 1329227697997490307154018925966130304

Offset: 2

Eric W. Weisstein, May 29 2017

nonn

Also the number of labeled simple graphs with n vertices whose edge-set is connected. - Gus Wiseman, Sep 11 2019

			From _Gus Wiseman_, Sep 11 2019: (Start)
The a(4) = 60 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}
  {13}  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {14}  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {23}  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {24}  {13,14}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {34}  {13,23}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
        {13,34}  {12,14,34}  {12,14,23,24}
        {14,24}  {12,23,24}  {12,14,23,34}
        {14,34}  {12,23,34}  {12,14,24,34}
        {23,24}  {12,24,34}  {12,23,24,34}
        {23,34}  {13,14,23}  {13,14,23,24}
        {24,34}  {13,14,24}  {13,14,23,34}
                 {13,14,34}  {13,14,24,34}
                 {13,23,24}  {13,23,24,34}
                 {13,23,34}  {14,23,24,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}             {12,13,14,23,24,34}
                 {23,24,34}
(End)

Andrew Howroyd, Table of n, a(n) for n = 2..50
Eric Weisstein's World of Mathematics, Triangular Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

The unlabeled version is A292300.

Cf. A001187, A006125, A327070, A327148, A327199, A327235.

Table[With[{g = GraphData[{"Triangular", n}]}, Total[Boole[ConnectedGraphQ[Subgraph[g, #]] & /@ Subsets[VertexList[g]]]]], {n, 2, 5}] - 1
(* Second program: *)
g[n_] := g[n] = If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k) * (n-k-1)/2)*g[k], {k, 1, n-1}]/n]; a[n_] := Sum[Binomial[n, i]*g[i], {i, 2, n}]; Table[a[n], {n, 2, 16}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

seq(n)={Vec(serlaplace(exp(x + O(x*x^n))*(-x+log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n))))))} \\ Andrew Howroyd, Sep 11 2019

a(n) = Sum_{i=2..n} binomial(n,i) * A001187(i). - Andrew Howroyd, Jun 07 2017
E.g.f.: exp(x)*(-x + log(Sum_{k>=0} 2^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Sep 11 2019
a(n) = A006125(n) - A327199(n). - Gus Wiseman, Sep 11 2019

Terms a(9) and beyond from Andrew Howroyd, Jun 07 2017

A182100 The number of connected simple labeled graphs with <= n nodes.

Original entry on oeis.org

1, 2, 4, 11, 65, 974, 31744, 2069971, 267270041, 68629753650, 35171000942708, 36024807353574291, 73784587576805254665, 302228602363365451957806, 2475873310144021668263093216, 40564787336902311168400640561099

Offset: 0

Geoffrey Critzer, Apr 11 2012

nonn

			From _Gus Wiseman_, Sep 03 2019: (Start)
The a(0) = 1 through a(3) = 11 edge-sets (singletons represent uncovered vertices):
  {}  {}     {}       {}
      {{1}}  {{1}}    {{1}}
             {{2}}    {{2}}
             {{1,2}}  {{3}}
                      {{1,2}}
                      {{1,3}}
                      {{2,3}}
                      {{1,2},{1,3}}
                      {{1,2},{2,3}}
                      {{1,3},{2,3}}
                      {{1,2},{1,3},{2,3}}
(End)

G. C. Greubel, Table of n, a(n) for n = 0..80

The unlabeled version is A292300(n) + 1.

Cf. A001187, A006129, A054592, A287689, A327070, A327075, A327078.

nn = 15; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Exp[x] (Log[g] + 1), {x, 0, nn}], x]

a(n) = Sum_{i=0..n} binomial(n,i)*A001187(i).
E.g.f.: exp(x)*A(x) where A(x) is e.g.f. for A001187.
a(n) = A327078(n) + n. - Gus Wiseman, Sep 03 2019

A383975 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-simplex up to isometries of the n-simplex, with 0 <= k <= A000217(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 3, 5, 6, 6, 4, 2, 1, 1, 1, 1, 1, 3, 5, 12, 19, 23, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 1, 3, 5, 12, 30, 56, 91, 128, 147, 147, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 1, 3, 5, 12, 30, 79, 180, 364, 633, 961, 1300, 1551, 1644, 1556, 1311, 980, 663, 402, 221, 115, 56, 24, 11, 5, 2, 1, 1

Offset: 0

Peter Kagey, May 16 2025

Connected subsets of edges are also called "polysticks", "polyedges", and "polyforms".
These are "free" polyforms, in that two polyforms are equivalent if one can be mapped to the other via the n! symmetries of the n-simplex.
Equivalently, T(n,k) is the number of connected unlabeled graphs with k edges and between 1 and n+1 vertices. - Pontus von Brömssen, May 27 2025

			Triangle begins:
 0 | 1;
 1 | 1, 1;
 2 | 1, 1, 1, 1;
 3 | 1, 1, 1, 3, 2, 1, 1;
 4 | 1, 1, 1, 3, 5, 6, 6, 4, 2, 1, 1;
 5 | 1, 1, 1, 3, 5, 12, 19, 23, 24, 21, 15, 9, 5, 2, 1, 1;
 6 | 1, 1, 1, 3, 5, 12, 30, 56, 91, 128, 147, 147, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1;

Peter Kagey, Illustration of row 3.

Cf. A333333 (cube, row 3), A383490 (dodecahedron), A383973 (octahedron, row 3), A383974 (icosahedron).

Cf. A000217, A002905, A292300.

T(n,n) = A002905(n).

The sum of row n is A292300(n+1)+1 for n >= 1. - Pontus von Brömssen, May 26 2025

Missing term a(62)=1 inserted and a(73)-a(91) added by Pontus von Brömssen, May 26 2025

cp's OEIS Frontend

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A182100 The number of connected simple labeled graphs with <= n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A383975 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-simplex up to isometries of the n-simplex, with 0 <= k <= A000217(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions