A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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

Crossrefs

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

Programs

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 *)

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

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)

Extensions

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