cp's OEIS Frontend

A213442 Number of 3-colored graphs on n labeled nodes.

%I A213442 N2303 #28 May 12 2025 06:46:15
%S A213442 0,0,48,1152,30720,1152000,65630208,5858721792,829548134400,
%T A213442 187058611814400,67238204562997248,38521444919968530432,
%U A213442 35161130697930162831360,51112782500104147115704320,118291364909478542785766227968,435713123445085638702895120515072,2553666760604861879125023961330483200
%N A213442 Number of 3-colored graphs on n labeled nodes.
%C A213442 A191371 counts labeled 3-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 3 or fewer colors. This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly three colors. Cf. A213441 and A224068. - _Peter Bala_, Apr 10 2013
%D A213442 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H A213442 Alois P. Heinz, <a href="/A213442/b213442.txt">Table of n, a(n) for n = 1..75</a>
%H A213442 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 A213442 R. P. Stanley, <a href="https://doi.org/10.1016/0012-365X(73)90108-8">Acyclic orientation of graphs</a>, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
%H A213442 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%H A213442 Wikipedia, <a href="http://en.wikipedia.org/wiki/Graph_coloring">Graph coloring</a>
%F A213442 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)^3 = 48*x^3/(3!*2^3) + 1152*x^4/(4!*2^6) + 30720*x^5/(5!*2^10) + ... (see Read). - _Peter Bala_, Apr 10 2013
%F A213442 a(n) = O(2^(n^2/3)*3^n/n). - _Vaclav Kotesovec_, Jul 23 2013
%p A213442 F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
%p A213442 F3:=n->add(binomial(n,r)*2^(r*(n-r))*F2(r),r=1..n-1);
%p A213442 [seq(F3(n),n=1..20)];
%t A213442 Table[Sum[Binomial[n,r]*2^(r*(n-r))*Sum[Binomial[r,s]*2^(s*(r-s)),{s,1,r-1}],{r,1,n-1}],{n,1,20}] (* _Vaclav Kotesovec_, Jul 23 2013 *)
%o A213442 (PARI) seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^3), -n)} \\ _Andrew Howroyd_, Nov 30 2018
%Y A213442 Cf. A191371, A213441, A224068.
%K A213442 nonn,easy
%O A213442 1,3
%A A213442 _N. J. A. Sloane_, Jun 12 2012