A213442 Number of 3-colored graphs on n labeled nodes.

0, 0, 48, 1152, 30720, 1152000, 65630208, 5858721792, 829548134400, 187058611814400, 67238204562997248, 38521444919968530432, 35161130697930162831360, 51112782500104147115704320, 118291364909478542785766227968, 435713123445085638702895120515072, 2553666760604861879125023961330483200

Offset: 1

Author

N. J. A. Sloane, Jun 12 2012

Keywords

• nonn
• easy

Comments

A191371 counts labeled 3-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 3 or fewer colors. This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly three colors. Cf. A213441 and A224068. - Peter Bala, Apr 10 2013

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..75
• 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. 5 (1973), 171-178. North Holland Publishing Company.
• Eric Weisstein's World of Mathematics, k-Colorable Graph
• Wikipedia, Graph coloring

Crossrefs

Cf. A191371, A213441, A224068.

Programs

Maple

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
F3:=n->add(binomial(n,r)*2^(r*(n-r))*F2(r),r=1..n-1);
[seq(F3(n),n=1..20)];

Mathematica

Table[Sum[Binomial[n,r]*2^(r*(n-r))*Sum[Binomial[r,s]*2^(s*(r-s)),{s,1,r-1}],{r,1,n-1}],{n,1,20}] (* Vaclav Kotesovec, Jul 23 2013 *)

PARI

seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^3), -n)} \\ Andrew Howroyd, Nov 30 2018

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 (E(x) - 1)^3 = 48*x^3/(3!*2^3) + 1152*x^4/(4!*2^6) + 30720*x^5/(5!*2^10) + ... (see Read). - Peter Bala, Apr 10 2013

a(n) = O(2^(n^2/3)*3^n/n). - Vaclav Kotesovec, Jul 23 2013