cp's OEIS Frontend

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

%I A287689 #28 Feb 16 2025 08:33:46
%S A287689 1,7,60,968,31737,2069963,267270032,68629753640,35171000942697,
%T A287689 36024807353574279,73784587576805254652,302228602363365451957792,
%U A287689 2475873310144021668263093201,40564787336902311168400640561083,1329227697997490307154018925966130304
%N A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.
%C A287689 Also the number of labeled simple graphs with n vertices whose edge-set is connected. - _Gus Wiseman_, Sep 11 2019
%H A287689 Andrew Howroyd, <a href="/A287689/b287689.txt">Table of n, a(n) for n = 2..50</a>
%H A287689 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TriangularGraph.html">Triangular Graph</a>
%H A287689 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%F A287689 a(n) = Sum_{i=2..n} binomial(n,i) * A001187(i). - _Andrew Howroyd_, Jun 07 2017
%F A287689 E.g.f.: exp(x)*(-x + log(Sum_{k>=0} 2^binomial(k, 2)*x^k/k!)). - _Andrew Howroyd_, Sep 11 2019
%F A287689 a(n) = A006125(n) - A327199(n). - _Gus Wiseman_, Sep 11 2019
%e A287689 From _Gus Wiseman_, Sep 11 2019: (Start)
%e A287689 The a(4) = 60 edge-sets:
%e A287689   {12}  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}
%e A287689   {13}  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
%e A287689   {14}  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
%e A287689   {23}  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
%e A287689   {24}  {13,14}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
%e A287689   {34}  {13,23}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
%e A287689         {13,34}  {12,14,34}  {12,14,23,24}
%e A287689         {14,24}  {12,23,24}  {12,14,23,34}
%e A287689         {14,34}  {12,23,34}  {12,14,24,34}
%e A287689         {23,24}  {12,24,34}  {12,23,24,34}
%e A287689         {23,34}  {13,14,23}  {13,14,23,24}
%e A287689         {24,34}  {13,14,24}  {13,14,23,34}
%e A287689                  {13,14,34}  {13,14,24,34}
%e A287689                  {13,23,24}  {13,23,24,34}
%e A287689                  {13,23,34}  {14,23,24,34}
%e A287689                  {13,24,34}
%e A287689                  {14,23,24}
%e A287689                  {14,23,34}
%e A287689                  {14,24,34}             {12,13,14,23,24,34}
%e A287689                  {23,24,34}
%e A287689 (End)
%t A287689 Table[With[{g = GraphData[{"Triangular", n}]}, Total[Boole[ConnectedGraphQ[Subgraph[g, #]] & /@ Subsets[VertexList[g]]]]], {n, 2, 5}] - 1
%t A287689 (* Second program: *)
%t A287689 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_ *)
%o A287689 (PARI) 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
%Y A287689 The unlabeled version is A292300.
%Y A287689 Cf. A001187, A006125, A327070, A327148, A327199, A327235.
%K A287689 nonn
%O A287689 2,2
%A A287689 _Eric W. Weisstein_, May 29 2017
%E A287689 Terms a(9) and beyond from _Andrew Howroyd_, Jun 07 2017