login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058873 Number of 3-colored labeled graphs with n nodes. 3
0, 0, 8, 192, 5120, 192000, 10938368, 976453632, 138258022400, 31176435302400, 11206367427166208, 6420240819994755072, 5860188449655027138560, 8518797083350691185950720, 19715227484913090464294371328, 72618853907514273117149186752512 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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]

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.

LINKS

Robert Israel, Table of n, a(n) for n = 1..97

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

FORMULA

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

MAPLE

E:= Sum(x^n/(n!*2^(n*(n-1)/2)), n=1..infinity):

G:= 1/6*E^3:

S:= series(G, x, 21):

seq(coeff(S, x, n)*n!*2^(n*(n-1)/2), n=1..20); # Robert Israel, Aug 01 2018

MATHEMATICA

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

PROG

(PARI)

N=66;  x='x+O('x^N);

E=sum(n=0, N, x^n/(n!*2^binomial(n, 2)) );

tgf=(E-1)^3/6;  v=concat([0, 0], Vec(tgf));

v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) )

/* Joerg Arndt, Apr 14 2013 */

CROSSREFS

A diagonal of A058843. A213442.

Sequence in context: A267948 A189537 A268095 * A052734 A003435 A071303

Adjacent sequences:  A058870 A058871 A058872 * A058874 A058875 A058876

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jan 07 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 07:44 EST 2018. Contains 317275 sequences. (Running on oeis4.)