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

%I M2954 N1192 #73 Oct 27 2023 18:25:40

%S 1,3,13,81,721,9153,165313,4244481,154732801,8005686273,587435092993,

%T 61116916981761,9011561121239041,1882834327457349633,

%U 557257804202631217153,233610656002563147038721,138681207656726645785559041

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

%C 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

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A000684/b000684.txt">Table of n, a(n) for n = 1..100</a> (first 32 terms from R. W. Robinson)

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a> (2*A000684)

%H 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 F. Harary and R. W. Robinson, <a href="http://dx.doi.org/10.4153/CJM-1979-007-3">Labeled bipartite blocks</a>, Canad. J. Math., 31 (1979), 60-68.

%H F. Harary and R. W. Robinson, <a href="/A001832/a001832.pdf">Labeled bipartite blocks</a>, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

%H D. A. Klarner, <a href="http://dx.doi.org/10.1016/S0021-9800(69)80100-6">The number of graded partially ordered sets</a>, J. Combin. Theory, 6 (1969), 12-19.

%H D. A. Klarner, <a href="/A000798/a000798_11.pdf">The number of graded partially ordered sets</a>, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]

%H A. Nymeyer and R. W. Robinson, <a href="/A000684/a000684.pdf">Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs</a>, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]

%H R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>

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

%F 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

%F From _Peter Bala_, Apr 01 2013: (Start)

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

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

%F 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)

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

%o (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

%Y 2 * A000683(n) + 1.

%Y Cf. A058872, A111636, A134531.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_

%E a(15) onwards added by _N. J. A. Sloane_, Oct 19 2006 from the Robinson reference