OFFSET
1,3
COMMENTS
A coloring of a simple graph is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color. A213441 counts those colorings of labeled graphs on n vertices that use exactly two colors. This sequence is 1/4 of A213441 (1/4 of column 2 of Table 1 in Read). - Peter Bala, Apr 11 2013
A047863 counts colorings of labeled graphs on n vertices that use two or fewer colors. - Peter Bala, Apr 11 2013
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, table 1.5.1, column 2 (divided by 2).
R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
T. D. Noe, Table of n, a(n) for n=1..50
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410—414.
FORMULA
Reference gives generating function.
a(n) ~ c * 2^(n^2/4+n-3/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013
MATHEMATICA
maxn = 16; t[_, 1] = 1; t[n_, k_] := t[n, k] = Sum[Binomial[n, j]*2^(j*(n - j))*t[j, k - 1]/k, {j, 1, n - 1}]; a[n_] := t[n, 2]/2; Table[a[n], {n, 1, maxn}] (* Jean-François Alcover, Sep 21 2011 *)
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Feb 02 2000
STATUS
approved