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

Offset: 1

Author

Peter Bala, Apr 10 2013

Keywords

• nonn
• easy

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

• 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

Crossrefs

Cf. A213441, A213442, A223887.

Programs

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

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

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