OFFSET
1,2
COMMENTS
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
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
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)
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 *)
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004
STATUS
approved