A058379 Essentially parallel series-parallel networks with n labeled edges, multiple edges not allowed.

0, 1, 0, 3, 7, 90, 676, 9058, 117286, 1934068, 34354196, 698971944, 15520697072, 379690093016, 10064445063128, 288507479108384, 8875736500909216, 291965748820524000, 10221371162528667136, 379535362671828005536, 14896748155197456096736

Offset

0,4

Links

Table of n, a(n) for n=0..20.

S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]

J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the sequence Q_n).

Index entries for sequences mentioned in Moon (1987)

Formula

E.g.f. satisfies A(x) = x + O(x^2), 2*A(x) = exp(A(x)) - 1 + log(1+x).

a(n) = sum(m=1..n, (sum(k=0..m-1, (m+k-1)!*sum(j=0..k, sum(i=0..j, ((-1)^i*2^i*Stirling2(m+j-i-1,j-i))/(i!*(m+j-i-1)!))/(k-j)!))) *Stirling1(n,m)). - Vladimir Kruchinin, Feb 17 2012

E.g.f.: -1/2 + log(1+x)/2 - LambertW(-exp(-1/2)*sqrt(1+x)/2). - Vaclav Kotesovec, Jan 08 2014

a(n) ~ n^(n-1) / (2*sqrt(2) * (4-exp(1))^(n-1/2)). - Vaclav Kotesovec, Jan 08 2014

Example

A(x) = x + 1/2*x^3 + 7/24*x^4 + 3/4*x^5 + 169/180*x^6 + ...
For n=4 there are two unlabeled networks:
..o.....o--o
./.\.../....\
o...o o------o
.\./
..o
which can be labeled in 3 (resp. 4) ways, for a total of 7.

Maple

Q := x; for d from 1 to 30 do Q := Q+c*x^(d+1)/(d+1)!; t1 := coeff(series(2*Q - (exp(Q)-1+log(1+x)), x, d+2), x, d+1); t2 := solve(t1, c); Q := subs(c=t2, Q); Q := series(Q, x, d+2); od: A058379 := n->coeff(Q, x, n)*n!; # method 1
Order := 50; t1 := solve(series((exp(A)-2*A-1), A)=-log(1+x), A); A058379 := n-> n!*coeff(t1, x, n); # method 2

Mathematica

CoefficientList[InverseSeries[Series[-1+E^(1+2*a-E^a), {a, 0, 20}], x], x]*Range[0, 20]! (* Jean-François Alcover, Jul 21 2011 *)
CoefficientList[Series[(-1 + Log[1+x] - 2*ProductLog[-Sqrt[1+x]/(2*Sqrt[E])])/2, {x, 0, 15}], x] * Range[0, 15]! (* Vaclav Kotesovec, Jan 08 2014 *)

Prog

(Maxima) a(n):=sum((sum((m+k-1)!*sum(sum(((-1)^i*2^i*stirling2(m+j-i-1, j-i))/(i!*(m+j-i-1)!), i, 0, j)/(k-j)!, j, 0, k), k, 0, m-1)) *stirling1(n, m), m, 1, n); /* Vladimir Kruchinin, Feb 17 2012 */
(PARI) Vec(serlaplace(-1/2 + log(1+x)/2 - lambertw(-exp(-.5)*sqrt(1+x)/2))) \/ 1 \\ Charles R Greathouse IV, Jun 16 2021

Crossrefs

Cf. A058380, A058381. See A000669 for unlabeled case when parallel edges are allowed.

Sequence in context: A064118 A041705 A137130 * A111002 A042481 A307661

Adjacent sequences: A058376 A058377 A058378 * A058380 A058381 A058382

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Dec 19 2000

Status

approved