login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058379 Essentially parallel series-parallel networks with n labeled edges, multiple edges not allowed. 9
0, 1, 0, 3, 7, 90, 676, 9058, 117286, 1934068, 34354196, 698971944, 15520697072, 379690093016, 10064445063128, 288507479108384, 8875736500909216, 291965748820524000, 10221371162528667136, 379535362671828005536, 14896748155197456096736 (list; graph; refs; listen; history; text; internal format)
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 */

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 22:40 EST 2020. Contains 331328 sequences. (Running on oeis4.)