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

%I #45 Oct 02 2024 14:37:10

%S 0,1,4,17,112,1449,40068,2350601,286192512,71213783665,35883905263780,

%T 36419649682706465,74221659280476136240,303193505953871645562969,

%U 2480118046704094643352358500,40601989176407026666590990422105,1329877330167226219547875498464516480

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

%C 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.

%C a(n) is the number of (non-null) subgraphs of the complete graph with n vertices. - _Maharshee K. Shah_, Sep 08 2024

%H Alois P. Heinz, <a href="/A004140/b004140.txt">Table of n, a(n) for n = 0..50</a>

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

%F E.g.f.: exp(x)*(A(x)-1), where A(x) is e.g.f. for A006125. - _Geoffrey Critzer_, Oct 09 2012

%F a(n) ~ 2^(n*(n-1)/2). - _Vaclav Kotesovec_, Nov 15 2014

%e n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}

%e ......................... 1 .. 2 .. 1 2 .. 1 2

%p a:= n-> add (binomial(n, k)*2^(k*(k-1)/2), k=1..n):

%p seq (a(n), n=0..20); # _Alois P. Heinz_, Oct 09 2012

%t 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 *)

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

%Y Cf. A006896.

%K nonn,nice

%O 0,3

%A _N. J. A. Sloane_, _Colin Mallows_, _James D. Klein_