A000684 Number of colored labeled n-node graphs with 2 interchangeable colors. (Formerly M2954 N1192)

1, 3, 13, 81, 721, 9153, 165313, 4244481, 154732801, 8005686273, 587435092993, 61116916981761, 9011561121239041, 1882834327457349633, 557257804202631217153, 233610656002563147038721, 138681207656726645785559041

Offset

1,2

Comments

a(n) = A058872(n) + 1. This sequence counts the empty graph on n nodes which is not allowed in A058872. - Geoffrey Critzer, Oct 07 2012

References

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

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

Vincenzo Librandi, Table of n, a(n) for n = 1..100 (first 32 terms from R. W. Robinson)

S. R. Finch, Bipartite, k-colorable and k-colored graphs (2*A000684)

S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]

F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.

F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.

D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]

A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]

R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

Formula

G.f.: A(x) = Sum_{n>=1} x^n/(1 - 2^n*x)^n. - Paul D. Hanna, Sep 14 2009

G.f.: 1/(W(0)-x) where W(k) = x*(x*2^k-1)^k - (x*2^(k+1)-1)^(k+1) + x*((2*x*2^k-1)^(2*k+2))/W(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012

From Peter Bala, Apr 01 2013: (Start)

a(n) = Sum_{k = 0..n-1} binomial(n-1,k)*2^(k*(n-k)).

a(n) = Sum_{k = 0..n} 2^k*A111636(n,k).

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with an offset of 0) is E(x)*E(2*x) = Sum_{n >= 0} a(n+1)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 13*x^2/(2!*2) + 81*x^3/(3!*2^3) + 721*x^4/(4!*2^6) + .... Cf. A134531. (End)

Mathematica

With[{nn=20}, Rest[CoefficientList[Series[Sum[x^n/(1-2^n x)^n, {n, nn}], {x, 0, nn}], x]]] (* Harvey P. Dale, Nov 24 2011 *)

Prog

(PARI) a(n)=polcoeff(sum(k=1, n, x^k/(1-2^k*x +x*O(x^n))^k), n) \\ Paul D. Hanna, Sep 14 2009

Crossrefs

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

Sequence in context: A005923 A335588 A089461 * A222272 A057993 A208810

Adjacent sequences: A000681 A000682 A000683 * A000685 A000686 A000687

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

a(15) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

Status

approved