A004140 Number of nonempty labeled simple graphs on nodes chosen from an n-set.

0, 1, 4, 17, 112, 1449, 40068, 2350601, 286192512, 71213783665, 35883905263780, 36419649682706465, 74221659280476136240, 303193505953871645562969, 2480118046704094643352358500, 40601989176407026666590990422105, 1329877330167226219547875498464516480

Offset: 0

Author

N. J. A. Sloane, Colin Mallows, James D. Klein

Keywords

• nonn
• nice

Comments

We are given n labeled points, we choose k (1 <= k <= n) of them and construct a simple (but not necessarily connected) graph on these k nodes in 2^C(k,2) ways.

a(n) is the number of (non-null) subgraphs of the complete graph with n vertices. - Maharshee K. Shah, Sep 08 2024

Examples

			n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}
......................... 1 .. 2 .. 1 2 .. 1 2
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..50

Crossrefs

Cf. A006896.

Programs

Maple

a:= n-> add (binomial(n, k)*2^(k*(k-1)/2), k=1..n):
seq (a(n), n=0..20);  # Alois P. Heinz, Oct 09 2012

Mathematica

nn=20;s=Sum[2^Binomial[n,2]x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[ Series[(s-1) Exp[x],{x,0,nn}],x]  (* Geoffrey Critzer, Oct 09 2012 *)

PARI

a(n)=sum(k=1,n,binomial(n,k)*2^((k^2-k)/2))

Formula

a(n) = Sum_{k=1..n} binomial(n, k)*2^(k(k-1)/2).

E.g.f.: exp(x)*(A(x)-1), where A(x) is e.g.f. for A006125. - Geoffrey Critzer, Oct 09 2012

a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, Nov 15 2014