cp's OEIS Frontend

A000686 Number of 4-colored labeled graphs on n nodes, divided by 4.

%I A000686 M4449 N1884 #52 May 10 2025 23:14:24
%S A000686 1,7,85,1777,63601,3882817,403308865,71139019777,21276992674561,
%T A000686 10778161937857537,9238819435213784065,13390649605615389843457,
%U A000686 32796747486424209782108161,135669064080920007649863745537,947468281528010179181982467702785,11166618111585805201637975219611631617
%N A000686 Number of 4-colored labeled graphs on n nodes, divided by 4.
%C A000686 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
%D A000686 R. C. Read, personal communication.
%D A000686 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000686 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000686 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a>. (4*{a(n)})
%H A000686 S. R. Finch, <a href="/A191371/a191371.pdf">Bipartite, k-colorable and k-colored graphs</a>, June 5, 2003. [Cached copy, with permission of the author]
%H A000686 R. C. Read, <a href="http://cms.math.ca/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%H A000686 R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>.
%F A000686 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
%F A000686 From _Peter Bala_, Apr 12 2013: (Start)
%F A000686 a(n) = (1/4)*A223887(n).
%F A000686 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)).
%F A000686 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)
%t A000686 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_ *)
%o A000686 (PARI)
%o A000686 N=66;  x='x+O('x^N);
%o A000686 E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
%o A000686 tgf=E^4-1;  v=Vec(tgf);
%o A000686 v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) ) / 4
%o A000686 /* _Joerg Arndt_, Apr 10 2013 */
%Y A000686 Cf. A000683, A000685, A223887.
%K A000686 nonn,easy,nice
%O A000686 1,2
%A A000686 _N. J. A. Sloane_
%E A000686 More terms from Pab Ter (pabrlos(AT)yahoo.com) and _Emeric Deutsch_, May 05 2004