login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.
(Formerly M1885)
21
1, 2, 8, 52, 472, 5504, 78416, 1320064, 25637824, 564275648, 13879795712, 377332365568, 11234698041088, 363581406419456, 12707452084972544, 477027941930515456, 19142041172838025216, 817675811320888020992, 37044610820729973813248, 1774189422608238694776832 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.

W. Knoedel, Über Zerfaellungen, Monatsh. Math., 55 (1951), 20-27.

Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.

P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.

P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619.

J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. U(x)).

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.

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

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.40(a), S(x).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..200

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

P. J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4. [From Aaron Meyerowitz, Sep 30 2010]

F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092, 2013

D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]

B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1 ), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.

S. R. Finch, Series-parallel networks

ISCGI, Cograph graphs

Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244

N. J. A. Sloane, Transforms

Index entries for reversions of series

Index entries for sequences mentioned in Moon (1987)

Index entries for sequences related to trees [From Aaron Meyerowitz, Sep 30 2010]

FORMULA

For n >= 2, A006351(n) = 2*A000311(n) = A005640(n)/2^n. Row sums of A140945.

E.g.f. is reversion of 2*log(1+x)-x.

Also exponential transform of A000311, define b by 1+sum b_n x^n / n! = exp ( 1 + sum a_n x^n /n!).

E.g.f.: A(x), B(x)=x*A(x) satisfies the differential equation B'(x)=(1+B(x))/(1-B(x)). - Vladimir Kruchinin, Jan 18 2011

From Peter Bala, Sep 05 2011: (Start)

The generating function A(x) satisfies the autonomous differential equation A'(x) = (1+A)/(1-A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-t)/(1+t) = 2*log(1+x)-x, which yields A(x) = -1-2*W(-1/2*exp((x-1)/2)), where W is the Lambert W function.

The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+x)/(1-x)*g(x)). Compare with A032188.

Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1+t)/(1-t) = 1 + 2*t + 2*t^2 + 2*t^3 + ..., leads to the following combinatorial interpretation for the sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >=1 can be in one of 2 colors. An example is given below. (End)

A134991 gives (b.+c.)^n = 0^n , for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011

G.f.: 1/S(0) where S(k) = 1 - x*(k+1) - x*(k+1)/S(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 18 2011

a(n) = ((n-1)!*sum(k=1..n-1, C(n+k-1,n-1)*sum(j=1..k, (-1)^(j)*C(k,j)* sum(l=0..j, (C(j,l)*(j-l)!*2^(j-l)*(-1)^l*stirling1(n-l+j-1,j-l))/ (n-l+j-1)!)))), n>1, a(1)=1. - Vladimir Kruchinin, Jan 24 2012

E.g.f.: A(x) = exp(A000311)-1. - Vladimir Kruchinin, Sep 25 2012

a(n) = sum_{k=0..n-1} A201637(n-1,k)*2^(n-k-1). - Peter Luschny, Nov 16 2012

G.f.: -1 + 2/Q(0), where Q(k)= 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013

a(n) ~ sqrt(2)*n^(n-1)/((2*log(2)-1)^(n-1/2)*exp(n)). - Vaclav Kotesovec, Jul 17 2013

G.f.: Q(0)/(1-x), where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 -x*(k+1))*(1 -x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2013

EXAMPLE

D^3(1) = (12*x^2+56*x+52)/(x-1)^6. Evaluated at x = 0 this gives a(4) = 52.

a(3) = 8: The 8 possible increasing plane trees on 3 vertices with vertices of outdegree k >= 1 coming in 2 colors, B or W, are

.......................................................

.1B..1B..1W..1W.....1B.......1W........1B........1W....

.|...|...|...|...../.\....../..\....../..\....../..\...

.2B..2W..2B..2W...2...3....2....3....3....2....3....2..

.|...|...|...|.........................................

.3...3...3...3.........................................

G.f. = x + 2*x^2 + 8*x^3 + 52*x^4 + 472*x^5 + 5504*x^6 + 78416*x^7 + ...

MAPLE

read transforms; t1 := 2*ln(1+x)-x; t2 := series(t1, x, 10); t3 := seriestoseries(t2, 'revogf'); t4 := SERIESTOLISTMULT(%);

# N denotes all series-parallel networks, S = series networks, P = parallel networks;

spec := [ N, N=Union(Z, S, P), S=Set(Union(Z, P), card>=2), P=Set(Union(Z, S), card>=2)}, labeled ]: A006351 := n->combstruct[count](spec, size=n);

A006351 := n -> add(combinat[eulerian2](n-1, k)*2^(n-k-1), k=0..n-1):

seq(A006351(n), n=1..18); # Peter Luschny, Nov 16 2012

MATHEMATICA

max = 18; f[x_] := 2*Log[1+x]-x; Rest[ CoefficientList[ InverseSeries[ Series[ f[x], {x, 0, max}], x], x]]*Range[max]! (* Jean-François Alcover, Nov 25 2011 *)

PROG

(Maxima) a(n):=if n=1 then 1 else ((n-1)!*sum(binomial(n+k-1, n-1)* sum((-1)^(j)*binomial(k, j)*sum((binomial(j, l)*(j-l)!*2^(j-l)*(-1)^l* stirling1(n-l+j-1, j-l))/(n-l+j-1)!, l, 0, j), j, 1, k), k, 1, n-1)); /* Vladimir Kruchinin, Jan 24 2012 */

(Sage)

def A006351(n): return add(A201637(n-1, k)*2^(n-k-1) for k in (0..n-1))

[A006351(n) for n in (1..18)]  # Peter Luschny, Nov 16 2012

(PARI) x='x+O('x^66); Vec(serlaplace(serreverse( 2*log(1+x) - 1*x ))) \\ Joerg Arndt, May 01 2013

CROSSREFS

Cf. A000311, A000084 (for unlabeled case), A032188. A140945.

Sequence in context: A125787 A007832 A111088 * A277499 A089467 A195192

Adjacent sequences:  A006348 A006349 A006350 * A006352 A006353 A006354

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 04:39 EST 2018. Contains 299358 sequences. (Running on oeis4.)