A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.
1, 5, 41, 545, 11681, 402305, 22207361, 1961396225, 276825510401, 62368881977345, 22413909724518401, 12840603873823473665, 11720394922432296755201, 17037597932370037286600705
Offset: 1
References
- R. C. Read, personal communication.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 1..50
- S. R. Finch, Bipartite, k-colorable and k-colored graphs (3*A000685)
- S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
- R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
- R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
- R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
- Eric Weisstein's World of Mathematics, k-Colorable Graph
Programs
-
Maple
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);
-
Mathematica
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 *)
Formula
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
From Peter Bala, Apr 12 2013: (Start)
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)
Extensions
More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004
Comments