login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000683 Number of colorings of labeled graphs on n nodes using exactly 2 colors, divided by 4.
(Formerly M4238 N1770)
11
0, 1, 6, 40, 360, 4576, 82656, 2122240, 77366400, 4002843136, 293717546496, 30558458490880, 4505780560619520, 941417163728674816, 278628902101315608576, 116805328001281573519360 (list; graph; refs; listen; history; text; internal format)
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
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
a(n)=(A047863(n)-2)/4.
A diagonal of A058843.
One quarter of A213441.
Sequence in context: A006387 A014481 A184266 * A352357 A143342 A084270
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Feb 02 2000
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:16 EDT 2024. Contains 371264 sequences. (Running on oeis4.)