OFFSET
0,3
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..50
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
EXAMPLE
n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}
......................... 1 .. 2 .. 1 2 .. 1 2
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 *)
PROG
(PARI) a(n)=sum(k=1, n, binomial(n, k)*2^((k^2-k)/2))
CROSSREFS
KEYWORD
nonn,nice,changed
AUTHOR
STATUS
approved