login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058872 Number of 2-colored labeled graphs with n nodes. 5
0, 2, 12, 80, 720, 9152, 165312, 4244480, 154732800, 8005686272, 587435092992, 61116916981760, 9011561121239040, 1882834327457349632, 557257804202631217152, 233610656002563147038720, 138681207656726645785559040, 116575238610106596799428165632 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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/2 of A213441 (1/2 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.

A. Mukhopadhyay, Lupanov decoding networks, in A. Mukhopadhyay, ed., Recent Developments in Switching Theory, Ac. Press, 1971, Chap. 3, see esp. p. 82 (number of shell functions).

LINKS

Table of n, a(n) for n=1..18.

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410—414.

MAPLE

A058872 := n->add(binomial(n, k)*2^(n-k)*2^(k*(n-k)), k=0..n-1);

MATHEMATICA

f[list_] := (Apply[Multinomial, list] * 2^((Total[list]^2 - Total[Table[list[[i]]^2, {i, 1, Length[list]}]])/2))/2!; Table[Total[Map[f, Select[Compositions[n, 2], Count[#, 0]==0&]]], {n, 1, 20}] (* Geoffrey Critzer, Oct 24 2011 *)

CROSSREFS

A diagonal of A058843.

One half of A213441.

Sequence in context: A063481 A185020 A052822 * A055548 A092850 A199420

Adjacent sequences:  A058869 A058870 A058871 * A058873 A058874 A058875

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Jan 07 2001

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 21 08:46 EDT 2014. Contains 240824 sequences.