

A058872


Number of 2colored 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 kcolored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410414.


MAPLE

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


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: A185020 A052822 A246018 * A055548 A092850 A199420
Adjacent sequences: A058869 A058870 A058871 * A058873 A058874 A058875


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane, Jan 07 2001


STATUS

approved



