login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A213442
Number of 3-colored graphs on n labeled nodes.
(Formerly N2303)
8
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
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
AUTHOR
N. J. A. Sloane, Jun 12 2012
STATUS
approved