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
KEYWORD
nonn,easy,changed
AUTHOR
N. J. A. Sloane, Jun 12 2012
STATUS
approved