A213441 Number of 2-colored graphs on n labeled nodes. (Formerly N1459)

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

Offset

1,2

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)

References

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

Links

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

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

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

Example

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

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

Prog

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

Crossrefs

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

Sequence in context: A069722 A343842 A027079 * A238299 A221656 A366623

Adjacent sequences: A213438 A213439 A213440 * A213442 A213443 A213444

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 11 2012

Status

approved