A058872 Number of 2-colored labeled graphs with n nodes.

0, 2, 12, 80, 720, 9152, 165312, 4244480, 154732800, 8005686272, 587435092992, 61116916981760, 9011561121239040, 1882834327457349632, 557257804202631217152, 233610656002563147038720, 138681207656726645785559040, 116575238610106596799428165632

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: A052822 A246018 A292933 * A340103 A055548 A092850

Adjacent sequences: A058869 A058870 A058871 * A058873 A058874 A058875

Keyword

nonn,easy

Author

N. J. A. Sloane, Jan 07 2001

Status

approved