login
This site is supported by donations 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

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

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

A diagonal of A058843.

One quarter of A213441.

Sequence in context: A006387 A014481 A184266 * A143342 A084270 A284195

Adjacent sequences:  A000680 A000681 A000682 * A000684 A000685 A000686

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 18:08 EDT 2018. Contains 316271 sequences. (Running on oeis4.)