cp's OEIS Frontend

A167939 The number of connected subgraphs of the complete graph with n nodes.

%I A167939 #21 Sep 09 2023 06:54:35
%S A167939 1,3,10,64,973,31743,2069970,267270040,68629753649,35171000942707,
%T A167939 36024807353574290,73784587576805254664,302228602363365451957805,
%U A167939 2475873310144021668263093215,40564787336902311168400640561098,1329227697997490307154018925966130320
%N A167939 The number of connected subgraphs of the complete graph with n nodes.
%C A167939 The problem originated from Attila Szabss.
%H A167939 G. C. Greubel, <a href="/A167939/b167939.txt">Table of n, a(n) for n = 1..80</a>
%F A167939 E.g.f.: exp(x)*log(A(x)) where A(x) is the e.g.f. for A006125. - _Geoffrey Critzer_, Nov 23 2016
%e A167939 For n = 3, consider the complete graph with nodes A, B and C. a(3) = 10, the 10 connected subgraphs being: A, B, C, AB, AC, BC, AB+AC, AB+BC, AC+BC, AB+AC+BC.
%t A167939 nn = 25;
%t A167939 g[z_]:= Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn}];
%t A167939 Drop[CoefficientList[Series[Exp[z]*Log[g[z]], {z,0,nn}], z]*Range[0, nn]!, 1] (* _Geoffrey Critzer_, Nov 23 2016 *)
%o A167939 (Haskell)
%o A167939 import Data.Function (fix)
%o A167939 import Data.List (transpose)
%o A167939 a :: [Integer]
%o A167939 a = scanl1 (+) . (!! 1) . transpose . fix $ map ((1:) . zipWith (*) (scanl1 (*) l) . zipWith poly (scanl1 (+) l)) . scanl (flip (:)) [] . zipWith (zipWith (*)) pascal where l = iterate (2*) 1
%o A167939 -- the Pascal triangle
%o A167939 pascal :: [[Integer]]
%o A167939 pascal = iterate (\l -> zipWith (+) (0: l) l) (1: repeat 0)
%o A167939 -- evaluate a polynomial at a given value
%o A167939 poly :: (Num a) => a -> [a] -> a
%o A167939 poly t = foldr (\e i -> e + t*i) 0
%o A167939 (Magma)
%o A167939 m:=35;
%o A167939 f:= func< x | (&+[2^Binomial(j,2)*x^j/Factorial(j): j in [0..m+2]]) >;
%o A167939 R<x>:=PowerSeriesRing(Rationals(), m);
%o A167939 Coefficients(R!(Laplace( Exp(x)*Log(f(x)) ))); // _G. C. Greubel_, Sep 08 2023
%o A167939 (SageMath)
%o A167939 m=35
%o A167939 def f(x): return sum(2^binomial(j,2)*x^j/factorial(j) for j in range(m+3))
%o A167939 def A167939_list(prec):
%o A167939     P.<x> = PowerSeriesRing(QQ, prec)
%o A167939     return P( exp(x)*log(f(x)) ).egf_to_ogf().list()
%o A167939 a=A167939_list(m); a[1:] # _G. C. Greubel_, Sep 08 2023
%Y A167939 Cf. A006125, A006896.
%K A167939 nonn
%O A167939 1,2
%A A167939 Peter Divianszky (divip(AT)aszt.inf.elte.hu), Nov 15 2009