A140945 -id:A140945 - cp's OEIS frontend

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

1, 2, 8, 52, 472, 5504, 78416, 1320064, 25637824, 564275648, 13879795712, 377332365568, 11234698041088, 363581406419456, 12707452084972544, 477027941930515456, 19142041172838025216, 817675811320888020992, 37044610820729973813248, 1774189422608238694776832

Offset: 1

N. J. A. Sloane

For a simple relationship to series-reduced rooted trees, partitions of n, and phylogenetic trees among other combinatoric constructs, see comments in A000311. - Tom Copeland, Jan 06 2021

			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 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
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. 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).

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.
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
Peter J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4. [From _Aaron Meyerowitz_, Sep 30 2010]
Frédéric Chapoton, Florent Hivert, and Jean-Christophe Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1 ), Ph. D. dissertation, Brandeis Univ., 2008.
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
ISCGI, Cograph graphs
Song He, Fei Teng, and Yong Zhang, String Correlators: Recursive Expansion, Integration-by-Parts and Scattering Equations, arXiv:1907.06041 [hep-th], 2019. Also in Journal of High Energy Physics (2019), 2019:85.
Walter Knödel, Über Zerfällungen, Monatsh. Math., 55 (1951), 20-27.
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
Michael D. Moffitt, Search Strategies for Topological Network Optimization, Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) (2022), 10299-10308.
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. U(x)).
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]

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

Cf. A133314, A134991, A135494.

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

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

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

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

# uses[eulerian2 from A201637]
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

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(B(x))-1 where B(x) is the e.g.f. of A000311. - 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
a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). - Ilya Gutkovskiy, Aug 28 2020
Conjecture: a(n) = A379459(n-2,0) = A379460(n-1,0) for n > 1 with a(1) = 1. - Mikhail Kurkov, Jan 16 2025

A359985 Triangle read by rows: T(n,k) is the number of quasi series-parallel matroids on [n] with rank k, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 35, 15, 1, 1, 31, 155, 155, 31, 1, 1, 63, 651, 1365, 651, 63, 1, 1, 127, 2667, 10941, 10941, 2667, 127, 1, 1, 255, 10795, 82215, 156597, 82215, 10795, 255, 1, 1, 511, 43435, 589135, 1988007, 1988007, 589135, 43435, 511, 1

Offset: 0

Andrew Howroyd, Mar 08 2023

A quasi series-parallel matroid is a collection of series-parallel matroids. See the Ferroni/Larson reference for a precise definition.

The first six rows of this triangle are the same as A022166.

			Triangle begins:
  1;
  1,   1;
  1,   3,    1;
  1,   7,    7,     1;
  1,  15,   35,    15,     1;
  1,  31,  155,   155,    31,    1;
  1,  63,  651,  1365,   651,   63,   1;
  1, 127, 2667, 10941, 10941, 2667, 127, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Luis Ferroni and Matt Larson, Kazhdan-Lusztig polynomials of braid matroids, arXiv:2303.02253 [math.CO], 2023.
Nicholas Proudfoot, Yuan Xu, and Ben Young, On the enumeration of series-parallel matroids, arXiv:2406.04502 [math.CO], 2024.

Row sums are A359986.
Columns k=0..2 are A000012, A000225, A006095.
Cf. A022166, A140945.

\\ Proposition 2.3, 2.8 in Ferroni/Larson, compare A140945.
T(n) = {[Vecrev(p) | p<-Vec(serlaplace(exp(x*(y+1) + y*intformal( serreverse(log(1 + x*y + O(x^n))/y + log(1 + x + O(x^n)) - x)))))]}
{ my(A=T(8)); for(i=1, #A, print(A[i])) }

A361355 Triangle read by rows: T(n,k) is the number of simple series-parallel matroids on [n] with rank k, 1 <= k <= n.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 15, 1, 0, 0, 0, 0, 75, 1, 0, 0, 0, 0, 735, 280, 1, 0, 0, 0, 0, 0, 9345, 938, 1, 0, 0, 0, 0, 0, 76545, 77805, 2989, 1, 0, 0, 0, 0, 0, 0, 1865745, 536725, 9285, 1, 0, 0, 0, 0, 0, 0, 13835745, 27754650, 3334870, 28446, 1, 0

Offset: 1

Andrew Howroyd, Mar 09 2023

			Triangle begins:
  1;
  0, 0;
  0, 1,  0;
  0, 0,  1,   0;
  0, 0, 15,   1,     0;
  0, 0,  0,  75,     1,     0;
  0, 0,  0, 735,   280,     1,    0;
  0, 0,  0,   0,  9345,   938,    1, 0;
  0, 0,  0,   0, 76545, 77805, 2989, 1, 0;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Luis Ferroni and Matt Larson, Kazhdan-Lusztig polynomials of braid matroids, arXiv:2303.02253 [math.CO], 2023.
Nicholas Proudfoot, Yuan Xu, and Ben Young, On the enumeration of series-parallel matroids, arXiv:2406.04502 [math.CO], 2024.

Row sums are A007834.
Cf. A140945, A359985, A361353.
Cf. A034941, A361282.

\\ B gives A359985 as e.g.f.
B(n)= {exp(x*(1+y) + y*intformal(serreverse(log(1 + x*y + O(x^n))/y + log(1 + x + O(x^n)) - x)))}
T(n) = {my(v=Vec(serlaplace(log(subst(B(n), x, log(1 + x + O(x*x^n)))/(1 + x))))); vector(#v, n, Vecrev(v[n]/y, n))}
{ my(A=T(9)); for(i=1, #A, print(A[i])) }

E.g.f.: A(x,y) = log(1 + B(x,y)) where B(x,y) is the e.g.f. of A361353.
E.g.f.: A(x,y) = log(B(log(1 + x), y)/(1 + x)) where B(x,y) is the e.g.f. of A359985.
T(2*n+1, n+1) = A034941(n).
T(2*n, n+1) = A361282(n).

A361353 Triangle read by rows: T(n,k) is the number of simple quasi series-parallel matroids on [n] with rank k, 1 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 5, 1, 0, 0, 15, 16, 1, 0, 0, 0, 175, 42, 1, 0, 0, 0, 735, 1225, 99, 1, 0, 0, 0, 0, 16065, 6769, 219, 1, 0, 0, 0, 0, 76545, 204400, 32830, 466, 1, 0, 0, 0, 0, 0, 2747745, 2001230, 147466, 968, 1, 0, 0, 0, 0, 0, 13835745, 56143395, 16813720, 632434, 1981, 1

Offset: 1

Andrew Howroyd, Mar 09 2023

See Table 2 in the Ferroni/Larson reference.

			Triangle begins:
  1;
  0, 1;
  0, 1,  1;
  0, 0,  5,   1;
  0, 0, 15,  16,     1;
  0, 0,  0, 175,    42,      1;
  0, 0,  0, 735,  1225,     99,     1;
  0, 0,  0,   0, 16065,   6769,   219,   1;
  0, 0,  0,   0, 76545, 204400, 32830, 466, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Luis Ferroni and Matt Larson, Kazhdan-Lusztig polynomials of braid matroids, arXiv:2303.02253 [math.CO], 2023.
Nicholas Proudfoot, Yuan Xu, and Ben Young, On the enumeration of series-parallel matroids, arXiv:2406.04502 [math.CO], 2024.

Row sums are A361354.

Cf. A140945, A359985, A361355.

\\ B gives A359985 as e.g.f.
B(n)= {exp(x*(1+y) + y*intformal(serreverse(log(1 + x*y + O(x^n))/y + log(1 + x + O(x^n)) - x)))}
T(n) = {[Vecrev(p/y) | p<-Vec(serlaplace(subst(B(n), x, log(1 + x + O(x*x^n)))/(1 + x) - 1))]}
{ my(A=T(9)); for(i=1, #A, print(A[i])) }

E.g.f.: A(x,y) = B(log(1 + x), y)/(1 + x) - 1 where B(x,y) is the e.g.f. of A359985.

cp's OEIS Frontend

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Sage

Formula

A359985 Triangle read by rows: T(n,k) is the number of quasi series-parallel matroids on [n] with rank k, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A361355 Triangle read by rows: T(n,k) is the number of simple series-parallel matroids on [n] with rank k, 1 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A361353 Triangle read by rows: T(n,k) is the number of simple quasi series-parallel matroids on [n] with rank k, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula