1,3

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

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

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.

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

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

a(n)=(A047863(n)-2)/4.

A diagonal of A058843.

One quarter of A213441.

Sequence in context: A006387 A014481 A184266 * A352357 A143342 A084270

Adjacent sequences: A000680 A000681 A000682 * A000684 A000685 A000686

nonn,nice,easy

More terms from Vladeta Jovovic, Feb 02 2000

approved