A213442 Number of 3-colored graphs on n labeled nodes. (Formerly N2303)

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

Offset

1,3

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

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

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

Prog

(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

Crossrefs

Cf. A191371, A213441, A224068.

Sequence in context: A290403 A035719 A035797 * A161693 A162193 A162461

Adjacent sequences: A213439 A213440 A213441 * A213443 A213444 A213445

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 12 2012

Status

approved