cp's OEIS Frontend

A237195 Number of simple labeled graphs on n nodes that contain some size k connected component, all of whose nodes are labeled with integers {1,2,...,k} for some k in {1,2,...,n}.

%I A237195 #11 Feb 05 2014 05:03:15
%S A237195 1,2,7,52,846,28628,1928768,255610528,66822534992,34632302913632,
%T A237195 35711543058158592,73426371674544520192,301419451958411673103360,
%U A237195 2472252535617096234970201088,40532629372281642451697543062528,1328660058258732602631909956943781888
%N A237195 Number of simple labeled graphs on n nodes that contain some size k connected component, all of whose nodes are labeled with integers {1,2,...,k} for some k in {1,2,...,n}.
%C A237195 In other words, a(n) is the number of simple labeled graphs on {1,2,...,n} such that 1 is an isolated node, or 1 and 2 form a size 2 component, or 1,2 and 3 form a size 3 component, or ... 1,2,3,...,k form a size k component, where 1<=k<=n.
%H A237195 Alois P. Heinz, <a href="/A237195/b237195.txt">Table of n, a(n) for n = 1..80</a>
%F A237195 a(n) = Sum_{k=1..n} A223894(n,k)/binomial(n,k).
%e A237195 a(3) = 7. We count all 8 simple labeled graphs on {1,2,3} except: 1-3 2.
%p A237195 b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
%p A237195       add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
%p A237195     end:
%p A237195 a:= n-> add(b(k)*2^((n-k)*(n-k-1)/2), k=1..n):
%p A237195 seq(a(n), n=1..20);  # _Alois P. Heinz_, Feb 04 2014
%t A237195 nn=15;g=Sum[2^Binomial[n,2]x^n/n!,{n,0,nn}];a=Drop[Range[0,nn]!CoefficientList[Series[Log[g],{x,0,nn}],x],1];Map[Total,Table[Table[Drop[Transpose[Table[ Range[0,nn]!CoefficientList[Series[a[[n]]x^n/n! g,{x,0,nn}],x],{n,1,nn}]],1][[i,j]]/Binomial[i,j],{j,1,i}],{i,1,nn}]]
%K A237195 nonn
%O A237195 1,2
%A A237195 _Geoffrey Critzer_, Feb 04 2014