cp's OEIS Frontend

A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.

%I A000685 M3995 N1656 #42 May 10 2025 23:14:28
%S A000685 1,5,41,545,11681,402305,22207361,1961396225,276825510401,
%T A000685 62368881977345,22413909724518401,12840603873823473665,
%U A000685 11720394922432296755201,17037597932370037286600705
%N A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.
%C A000685 Sequence represents 1/3 of the number of 3-colored labeled graphs on n nodes. Indeed, on p. 413 of the Read paper, column 3 is 3, 15, 123, 1635, ...; or see A047863. - _Emeric Deutsch_, May 06 2004
%D A000685 R. C. Read, personal communication.
%D A000685 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000685 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000685 T. D. Noe, <a href="/A000685/b000685.txt">Table of n, a(n) for n = 1..50</a>
%H A000685 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a> (3*A000685)
%H A000685 S. R. Finch, <a href="/A191371/a191371.pdf">Bipartite, k-colorable and k-colored graphs</a>, June 5, 2003. [Cached copy, with permission of the author]
%H A000685 R. C. Read, <a href="http://cms.math.ca/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%H A000685 R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>
%H A000685 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf">Acyclic orientation of graphs</a> Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
%H A000685 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%F A000685 a(n) = (1/3)Sum_{j=0..n} binomial(n, j)*2^(j(n-j))*c(j) where c(n) = Sum_{i=0..n} binomial(n, i)*2^(i(n-i)) = A047863(n). - _Emeric Deutsch_, May 06 2004
%F A000685 From _Peter Bala_, Apr 12 2013: (Start)
%F A000685 a(n) = 1/3*A191371(n). Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/3*E(x)^3 - 1/3 = Sum_{n >= 1} a(n)*x^n/(n!*2^C(n,2)) = x + 5*x^2/(2!*2) + 41*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Read). For examples see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)
%p A000685 c[0]:=1: for n from 1 to 30 do c[n]:=sum(binomial(n,i)*2^(i*(n-i)),i=0..n) od: a:=n->(1/3)*sum(binomial(n,j)*2^(j*(n-j))*c[j],j=0..n): seq(a(n),n=1..19);
%t A000685 a[n_] := 1/3*Sum[ 2^((i-j)*j + i*(n-i))*Binomial[n, i]*Binomial[i, j], {i, 0, n}, {j, 0, i}]; Table[ a[n], {n, 1, 14}] (* _Jean-François Alcover_, Dec 07 2011, after _Emeric Deutsch_ *)
%Y A000685 Cf. A000683, A047863, A191371, A223887.
%K A000685 nonn,easy,nice
%O A000685 1,2
%A A000685 _N. J. A. Sloane_
%E A000685 More terms from Pab Ter (pabrlos(AT)yahoo.com) and _Emeric Deutsch_, May 05 2004