cp's OEIS Frontend

A058873 Number of 3-colored labeled graphs with n nodes.

%I A058873 #28 Aug 01 2018 15:55:07
%S A058873 0,0,8,192,5120,192000,10938368,976453632,138258022400,31176435302400,
%T A058873 11206367427166208,6420240819994755072,5860188449655027138560,
%U A058873 8518797083350691185950720,19715227484913090464294371328,72618853907514273117149186752512
%N A058873 Number of 3-colored labeled graphs with n nodes.
%C A058873 A coloring of a simple graph is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color. A213442 counts those colorings of labeled graphs on n vertices that use exactly three colors. In this sequence, graph colorings that differ only by a permutation of the three colors are considered to be the same. Hence a(n) = 1/3!*A213442(n). [_Peter Bala_, Apr 12 2013]
%D A058873 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.
%H A058873 Robert Israel, <a href="/A058873/b058873.txt">Table of n, a(n) for n = 1..97</a>
%H A058873 R. C. Read, <a href="http://cms.math.ca/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%F A058873 Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function is 1/6*(E(x) - 1)^3 = 8*x^3/(3!*2^3) + 192*x^4/(4!*2^6) + 5120*x^5/(5!*2^10) + ... (see Read). - _Peter Bala_, Apr 13 2013
%p A058873 E:= Sum(x^n/(n!*2^(n*(n-1)/2)),n=1..infinity):
%p A058873 G:= 1/6*E^3:
%p A058873 S:= series(G,x,21):
%p A058873 seq(coeff(S,x,n)*n!*2^(n*(n-1)/2),n=1..20); # _Robert Israel_, Aug 01 2018
%t A058873 f[list_] := (Apply[Multinomial, list] * 2^((Total[list]^2-Total[Table[list[[i]]^2, {i, 1, Length[list]}]])/2))/3!; Table[Total[Map[f, Select[Compositions[n, 3], Count[#, 0]==0&]]], {n, 1, 20}] (* _Geoffrey Critzer_, Oct 24 2011 *)
%o A058873 (PARI)
%o A058873 N=66;  x='x+O('x^N);
%o A058873 E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
%o A058873 tgf=(E-1)^3/6;  v=concat([0,0], Vec(tgf));
%o A058873 v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) )
%o A058873 /* _Joerg Arndt_, Apr 14 2013 */
%Y A058873 A diagonal of A058843. A213442.
%K A058873 nonn
%O A058873 1,3
%A A058873 _N. J. A. Sloane_, Jan 07 2001