A224068 - OEIS

A224068

Number of labeled graphs on n vertices that can be colored using exactly 4 colors.

0, 0, 0, 1536, 122880, 10813440, 1348730880, 261070258176, 81787921367040, 42364317235937280, 36686317873382031360, 53408511909378681470976, 131046345314766385022238720, 542471805171085602081503969280, 3789399960645715708906355231293440

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

A223887 counts labeled 4-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 4 or fewer colors.

This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly 4 colors. Cf. A213441 and A213442.

LINKS

Table of n, a(n) for n=1..15.

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

R. P. Stanley, Acyclic orientation of graphs, Discrete Math., Volume 306, Issues 10-11, 28 May 2006, Pages 905-909.

Eric Weisstein's World of Mathematics, k-Colorable Graph

Wikipedia, Graph coloring

FORMULA

a(n) = Sum_{k=2..n-2} C(n,k)*2^(k*(n-k))*A213441(k)*A213441(n-k).

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 (E(x) - 1)^4 = 1536*x^4/(4!*2^6) + 122880*x^5/(5!*2^10) + 10813440*x^6/(6!*2^15) + ... + a(n)*x^n/(n!*2^(n*(n-1)/2)) + ... (see Read).

MATHEMATICA

nn=20; e[x_]:=Sum[x^n/(n!*2^Binomial[n, 2]), {n, 0, nn}]; Table[n!*2^Binomial[n, 2], {n, 0, nn}]CoefficientList[Series[(e[x]-1)^4, {x, 0, nn}], x] (* Geoffrey Critzer, Aug 11 2014 *)

PROG

(PARI)

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

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

tgf=(E-1)^4;

v=concat([0, 0, 0], Vec(tgf));

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

/* Joerg Arndt, Apr 10 2013 */

CROSSREFS

Cf. A213441, A213442, A223887.

Sequence in context: A203981 A188788 A170793 * A223245 A231320 A223377

Adjacent sequences: A224065 A224066 A224067 * A224069 A224070 A224071

KEYWORD

nonn,easy,changed

AUTHOR

Peter Bala, Apr 10 2013

STATUS

approved