OFFSET
1,2
COMMENTS
Sequence represents 1/4 of the number of 4-colored labeled graphs on n nodes. Indeed, on p. 413 of the Read paper, column 4 is 4, 28, 340, 7108, ... - 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
S. R. Finch, Bipartite, k-colorable and k-colored graphs. (4*{a(n)})
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.
FORMULA
a(n) = (1/4)*Sum_{k=0..n} binomial(n, k)*2^(k(n-k))*b(k), where b(0)=1 and b(k) = 3*A000685(k) for k > 0. - Emeric Deutsch, May 06 2004
From Peter Bala, Apr 12 2013: (Start)
a(n) = (1/4)*A223887(n).
a(n) = (1/4)*Sum_{k = 0..n} binomial(n,k)*2^(k*(n-k))*b(k)*b(n-k), where b(n) := Sum_{k = 0..n} binomial(n,k)*2^(k*(n-k)).
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is (1/4)*(E(x)^4 - 1) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = x + 7*x^2/(2!*2) + 85*x^3/(3!*2^3) + .... (End)
MATHEMATICA
b[n_] := Sum[ 2^((i-j)*j + i*(n-i))*Binomial[n, i]*Binomial[i, j], {i, 0, n}, {j, 0, i}]; a[n_] := 1/4*Sum[ Binomial[n, k]*2^(k*(n-k))*b[k], {k, 0, n}]; Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Dec 07 2011, after Emeric Deutsch *)
PROG
(PARI)
N=66; x='x+O('x^N);
E=sum(n=0, N, x^n/(n!*2^binomial(n, 2)) );
tgf=E^4-1; v=Vec(tgf);
v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) ) / 4
/* Joerg Arndt, Apr 10 2013 */
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004
STATUS
approved