A000685 Number of 3-colored labeled graphs on n nodes, divided by 3. (Formerly M3995 N1656)

1, 5, 41, 545, 11681, 402305, 22207361, 1961396225, 276825510401, 62368881977345, 22413909724518401, 12840603873823473665, 11720394922432296755201, 17037597932370037286600705

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

Cf. A000683, A047863, A191371, A223887.

Sequence in context: A347951 A275787 A009755 * A144286 A246760 A073854

Adjacent sequences: A000682 A000683 A000684 * A000686 A000687 A000688

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004

Status

approved