OFFSET
0,2
COMMENTS
Cf. A213442, which counts colorings of labeled graphs on n vertices using exactly 3 colors. For 3-colorable labeled graphs on n vertices see A076315. - Peter Bala, Apr 12 2013
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, 16-18.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..50
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
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
FORMULA
a(n) = Sum(C(n,k)*C(n-k,r)*2^(k*r+k*m+r*m)) where the sum is taken over all nonnegative solutions to k + r + m = n.
From Peter Bala, Apr 12 2013: (Start)
a(n) = Sum_{k = 0..n} binomial(n,k)*2^(k*(n-k))*A047863(k).
a(n)= 3*A000685(n) for n >= 1.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^3 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 15*x^2/(2!*2) + 123*x^3/(3!*2^3) + 1635*x^4/(4!*2^6) + ....
EXAMPLE
a(2) = 15: There are two labeled 3-colorable graphs on 2 nodes, namely
A) 1 2 B) 1 2
o o o----o
Using 3 colors there are 9 ways to color the graph of type A and 3*2 = 6 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 15 labeled 3-colored graphs on 2 vertices.
MATHEMATICA
f[{k_, r_, m_}]:= Binomial[m+r+k, k] Binomial[m+r, r] 2^ (k r + k m + r m); Table[Total[Map[f, Compositions[n, 3]]], {n, 0, 20}]
PROG
(Python)
from sympy import binomial
def a047863(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)])
def a(n): return sum([binomial(n, k)*2**(k*(n - k))*a047863(k) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017
(PARI) seq(n)={my(p=(sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))^3); Vecrev(sum(j=0, n, j!*2^binomial(j, 2)*polcoef(p, j)*x^j))} \\ Andrew Howroyd, Dec 03 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Geoffrey Critzer, Jun 01 2011
STATUS
approved