cp's OEIS Frontend

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

%I A213441 N1459 #41 May 12 2025 06:46:20
%S A213441 0,4,24,160,1440,18304,330624,8488960,309465600,16011372544,
%T A213441 1174870185984,122233833963520,18023122242478080,3765668654914699264,
%U A213441 1114515608405262434304,467221312005126294077440,277362415313453291571118080,233150477220213193598856331264,277465561009648882424932436803584,467466753447825987214906927108587520
%N A213441 Number of 2-colored graphs on n labeled nodes.
%C A213441 From _Peter Bala_, Apr 10 2013: (Start)
%C A213441 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.
%C A213441 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).
%C A213441 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.
%C A213441 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)
%D A213441 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H A213441 R. C. Read, <a href="https://doi.org/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%H A213441 R. P. Stanley, <a href="https://doi.org/10.1016/j.disc.2006.03.010">Acyclic orientation of graphs</a>, Discrete Math. Volume 306, Issues 10-11, 28 May 2006, Pages 905-909.
%H A213441 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%H A213441 Wikipedia, <a href="http://en.wikipedia.org/wiki/Graph_coloring">Graph coloring</a>
%F A213441 From _Peter Bala_, Apr 10 2013: (Start)
%F A213441 a(n) = Sum_{k = 1..n-1} binomial(n,k)*2^(k*(n-k)). a(n) = A047863(n) - 2.
%F A213441 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) + ....
%F A213441 Sequence is 1/2*(column 2) from A058843. (End)
%F A213441 E.g.f.: Sum_{n>=1}(exp(2^n*x)-1)*x^n/n!. - _Geoffrey Critzer_, Aug 11 2014
%e A213441 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
%e A213441 ....1....2............1....2
%e A213441 ....o....*............*----o
%e A213441 ...........................
%e A213441 ....1....2............1....2
%e A213441 ....*....o............o----*
%e A213441 - _Peter Bala_, Apr 10 2013
%p A213441 F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
%p A213441 [seq(F2(n),n=1..20)];
%t A213441 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 *)
%o A213441 (PARI) a(n) = sum(k=1,n-1, binomial(n,k)*2^(k*(n-k)) ); /* _Joerg Arndt_, Apr 10 2013 */
%Y A213441 Cf. A047863, A058843, A191371, A213442, A223887, A224068.
%K A213441 nonn,easy
%O A213441 1,2
%A A213441 _N. J. A. Sloane_, Jun 11 2012