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.
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
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
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Jun 11 2012
STATUS
approved