|
%I M3995 N1656 #38 Apr 14 2019 13:09:08
%S 1,5,41,545,11681,402305,22207361,1961396225,276825510401,
%T 62368881977345,22413909724518401,12840603873823473665,
%U 11720394922432296755201,17037597932370037286600705
%N Number of 3-colored labeled graphs on n nodes, divided by 3.
%C 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 R. C. Read, personal communication.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000685/b000685.txt">Table of n, a(n) for n = 1..50</a>
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a> (3*A000685)
%H 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 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 R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%F 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 From _Peter Bala_, Apr 12 2013: (Start)
%F 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 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 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 Cf. A000683, A047863, A191371, A223887.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
%E More terms from Pab Ter (pabrlos(AT)yahoo.com) and _Emeric Deutsch_, May 05 2004
|
