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

Author

N. J. A. Sloane, Jan 07 2001

Keywords

• nonn
• easy

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

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

Crossrefs

A diagonal of A058843.

One half of A213441.

Programs

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 *)