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

1, 3, 10, 64, 973, 31743, 2069970, 267270040, 68629753649, 35171000942707, 36024807353574290, 73784587576805254664, 302228602363365451957805, 2475873310144021668263093215, 40564787336902311168400640561098, 1329227697997490307154018925966130320

Offset

1,2

Comments

The problem originated from Attila Szabss.

Links

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

Formula

E.g.f.: exp(x)*log(A(x)) where A(x) is the e.g.f. for A006125. - Geoffrey Critzer, Nov 23 2016

Example

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.

Mathematica

nn = 25;
g[z_]:= Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn}];
Drop[CoefficientList[Series[Exp[z]*Log[g[z]], {z, 0, nn}], z]*Range[0, nn]!, 1] (* Geoffrey Critzer, Nov 23 2016 *)

Prog

(Haskell)
import Data.Function (fix)
import Data.List (transpose)
a :: [Integer]
a = scanl1 (+) . (!! 1) . transpose . fix $ map ((1:) . zipWith (*) (scanl1 (*) l) . zipWith poly (scanl1 (+) l)) . scanl (flip (:)) [] . zipWith (zipWith (*)) pascal where l = iterate (2*) 1
-- the Pascal triangle
pascal :: [[Integer]]
pascal = iterate (\l -> zipWith (+) (0: l) l) (1: repeat 0)
-- evaluate a polynomial at a given value
poly :: (Num a) => a -> [a] -> a
poly t = foldr (\e i -> e + t*i) 0
(Magma)
m:=35;
f:= func< x | (&+[2^Binomial(j, 2)*x^j/Factorial(j): j in [0..m+2]]) >;
R<x>:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( Exp(x)*Log(f(x)) ))); // G. C. Greubel, Sep 08 2023
(SageMath)
m=35
def f(x): return sum(2^binomial(j, 2)*x^j/factorial(j) for j in range(m+3))
def A167939_list(prec):
    P.<x> = PowerSeriesRing(QQ, prec)
    return P( exp(x)*log(f(x)) ).egf_to_ogf().list()
a=A167939_list(m); a[1:] # G. C. Greubel, Sep 08 2023

Crossrefs

Cf. A006125, A006896.

Sequence in context: A041014 A367641 A237998 * A352766 A206724 A306187

Adjacent sequences: A167936 A167937 A167938 * A167940 A167941 A167942

Keyword

nonn

Author

Peter Divianszky (divip(AT)aszt.inf.elte.hu), Nov 15 2009

Status

approved