cp's OEIS Frontend

A224068 Number of labeled graphs on n vertices that can be colored using exactly 4 colors.

%I A224068 #22 May 12 2025 06:46:00
%S A224068 0,0,0,1536,122880,10813440,1348730880,261070258176,81787921367040,
%T A224068 42364317235937280,36686317873382031360,53408511909378681470976,
%U A224068 131046345314766385022238720,542471805171085602081503969280,3789399960645715708906355231293440
%N A224068 Number of labeled graphs on n vertices that can be colored using exactly 4 colors.
%C A224068 A223887 counts labeled 4-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 4 or fewer colors.
%C A224068 This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly 4 colors. Cf. A213441 and A213442.
%H A224068 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 A224068 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 A224068 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%H A224068 Wikipedia, <a href="http://en.wikipedia.org/wiki/Graph_coloring">Graph coloring</a>
%F A224068 a(n) = Sum_{k=2..n-2} C(n,k)*2^(k*(n-k))*A213441(k)*A213441(n-k).
%F A224068 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)^4 = 1536*x^4/(4!*2^6) + 122880*x^5/(5!*2^10) + 10813440*x^6/(6!*2^15) + ... + a(n)*x^n/(n!*2^(n*(n-1)/2)) + ... (see Read).
%t A224068 nn=20;e[x_]:=Sum[x^n/(n!*2^Binomial[n,2]),{n,0,nn}];Table[n!*2^Binomial[n,2],{n,0,nn}]CoefficientList[Series[(e[x]-1)^4,{x,0,nn}],x] (* _Geoffrey Critzer_, Aug 11 2014 *)
%o A224068 (PARI)
%o A224068 N=16;  x='x+O('x^N);
%o A224068 E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
%o A224068 tgf=(E-1)^4;
%o A224068 v=concat([0,0,0], Vec(tgf));
%o A224068 v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) )
%o A224068 /* _Joerg Arndt_, Apr 10 2013 */
%Y A224068 Cf. A213441, A213442, A223887.
%K A224068 nonn,easy
%O A224068 1,4
%A A224068 _Peter Bala_, Apr 10 2013