cp's OEIS Frontend

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

%I A004140 #45 Oct 02 2024 14:37:10
%S A004140 0,1,4,17,112,1449,40068,2350601,286192512,71213783665,35883905263780,
%T A004140 36419649682706465,74221659280476136240,303193505953871645562969,
%U A004140 2480118046704094643352358500,40601989176407026666590990422105,1329877330167226219547875498464516480
%N A004140 Number of nonempty labeled simple graphs on nodes chosen from an n-set.
%C A004140 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 A004140 a(n) is the number of (non-null) subgraphs of the complete graph with n vertices. - _Maharshee K. Shah_, Sep 08 2024
%H A004140 Alois P. Heinz, <a href="/A004140/b004140.txt">Table of n, a(n) for n = 0..50</a>
%F A004140 a(n) = Sum_{k=1..n} binomial(n, k)*2^(k(k-1)/2).
%F A004140 E.g.f.: exp(x)*(A(x)-1), where A(x) is e.g.f. for A006125. - _Geoffrey Critzer_, Oct 09 2012
%F A004140 a(n) ~ 2^(n*(n-1)/2). - _Vaclav Kotesovec_, Nov 15 2014
%e A004140 n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}
%e A004140 ......................... 1 .. 2 .. 1 2 .. 1 2
%p A004140 a:= n-> add (binomial(n, k)*2^(k*(k-1)/2), k=1..n):
%p A004140 seq (a(n), n=0..20);  # _Alois P. Heinz_, Oct 09 2012
%t A004140 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 A004140 (PARI) a(n)=sum(k=1,n,binomial(n,k)*2^((k^2-k)/2))
%Y A004140 Cf. A006896.
%K A004140 nonn,nice
%O A004140 0,3
%A A004140 _N. J. A. Sloane_, _Colin Mallows_, _James D. Klein_