A213441 Number of 2-colored graphs on n labeled nodes.

0, 4, 24, 160, 1440, 18304, 330624, 8488960, 309465600, 16011372544, 1174870185984, 122233833963520, 18023122242478080, 3765668654914699264, 1114515608405262434304, 467221312005126294077440, 277362415313453291571118080, 233150477220213193598856331264, 277465561009648882424932436803584, 467466753447825987214906927108587520

Offset: 1

Author

N. J. A. Sloane, Jun 11 2012

Keywords

• nonn
• easy

Comments

From Peter Bala, Apr 10 2013: (Start)

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. This sequence counts only those colorings of labeled graphs on n vertices that use exactly two colors.

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then Read has shown that (E(x) - 1)^k is a generating function for counting labeled graphs colored using precisely k colors. This is the case k = 2. For other cases see A213442 (k = 3) and A224068 (k = 4).

A coloring of a graph G that uses k or fewer colors is called a k-coloring of G. The graph G is k-colored if a k-coloring of G exists.

Then E(x)^k is a generating function for the enumeration of labeled k-colored graphs on n vertices (see Stanley). For cases see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)

Examples

			a(2) = 4: Denote the vertex coloring by o and *. The 4 labeled graphs on 2 vertices that can be colored using exactly two colors are
....1....2............1....2
....o....*............*----o
...........................
....1....2............1....2
....*....o............o----*
- _Peter Bala_, Apr 10 2013
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Links

• R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
• R. P. Stanley, Acyclic orientation of graphs, Discrete Math. Volume 306, Issues 10-11, 28 May 2006, Pages 905-909.
• Eric Weisstein's World of Mathematics, k-Colorable Graph
• Wikipedia, Graph coloring

Crossrefs

Cf. A047863, A058843, A191371, A213442, A223887, A224068.

Programs

Maple

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
[seq(F2(n),n=1..20)];

Mathematica

nn=20;a[x_]:=Sum[x^n/(n!*(2^(n^2/2))),{n,0,nn}];Drop[Table[n!*(2^(n^2/2)),{n,0,nn}]CoefficientList[Series[(a[x]-1)^2,{x,0,nn}],x],1] (* Geoffrey Critzer, Aug 05 2014 *)

PARI

a(n) = sum(k=1,n-1, binomial(n,k)*2^(k*(n-k)) ); /* Joerg Arndt, Apr 10 2013 */

Formula

From Peter Bala, Apr 10 2013: (Start)

a(n) = Sum_{k = 1..n-1} binomial(n,k)*2^(k*(n-k)). a(n) = A047863(n) - 2.

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function is (E(x) - 1)^2 = 4*x^2/(2!*2) + 24*x^3/(3!*2^3) + 160*x^4/(4!*2^6) + ....

Sequence is 1/2*(column 2) from A058843. (End)

E.g.f.: Sum_{n>=1}(exp(2^n*x)-1)*x^n/n!. - Geoffrey Critzer, Aug 11 2014