|
|
A000685
|
|
Number of 3-colored labeled graphs on n nodes, divided by 3.
(Formerly M3995 N1656)
|
|
3
|
|
|
1, 5, 41, 545, 11681, 402305, 22207361, 1961396225, 276825510401, 62368881977345, 22413909724518401, 12840603873823473665, 11720394922432296755201, 17037597932370037286600705
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
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
|
|
|
|