A000084 -id:A000084 - cp's OEIS frontend

A058381 Number of series-parallel networks with n labeled edges, multiple edges not allowed.

0, 1, 1, 4, 20, 156, 1472, 17396, 239612, 3827816, 69071272, 1394315088, 31081310944, 758901184432, 20135117147056, 576927779925568, 17752780676186432, 583910574851160000, 20443098012485430272, 759064322969950283072, 29793617955495321025472

Offset: 0

N. J. A. Sloane, Dec 19 2000

Steven R. Finch, Series-parallel networks
Steven 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 V_n).
Index entries for sequences mentioned in Moon (1987)

Equals A058379 + A058380.

Cf. A006351.

max=19; f[x_] := -2*ProductLog[-Sqrt[1+x]/(2*Sqrt[E])]-1;
CoefficientList[Series[f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, May 21 2012, after Vladeta Jovovic *)

a(n):=sum((sum((m+k-1)!*sum(((-1)^j*sum((2^(j-l)*(-1)^l *stirling1(m-l+j-1,j-l))/(l!*(m-l+j-1)!),l,0,j))/(k-j)!,j,0,k),k,0,m-1)) *stirling1(n,m),m,1,n); /* Vladimir Kruchinin, Feb 17 2012 */

E.g.f.: -2*LambertW(-1/2*exp(-1/2)*(1+x)^(1/2))-1. - Vladeta Jovovic, Aug 21 2006
a(n) = Sum(m=1..n, (Sum(k=0..m-1, (m+k-1)!*Sum(j=0..k, ((-1)^j *Sum(L=0..j, (2^(j-l)*(-1)^L*Stirling1(m-L+j-1,j-L))/(l!*(m-L+j-1)!)))/(k-j)!)))*Stirling1(n,m)). - Vladimir Kruchinin, Feb 17 2012
a(n) ~ n^(n-1) / (sqrt(2) * (4-exp(1))^(n-1/2)). - Vaclav Kotesovec, Jul 09 2013
a(n) = Sum_{k=1..n} Stirling1(n, k) * A006351(k), n > 0. - Sean A. Irvine, Feb 03 2018

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

Original entry on oeis.org

0, 0, 1, 1, 13, 66, 796, 8338, 122326, 1893748, 34717076, 695343144, 15560613872, 379211091416, 10070672083928, 288420300817184, 8877044175277216, 291944826030636000, 10221726849956763136, 379528960298122277536, 14896869800297864928736

Offset: 0

N. J. A. Sloane, Dec 19 2000

Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the sequence R_n).
Index entries for sequences mentioned in Moon (1987)

Cf. A058379, A058381.

CoefficientList[Series[-1/2 - Log[1+x]/2 - LambertW[-E^(-1/2)*Sqrt[1+x]/2], {x, 0, 15}], x]* Range[0, 15]! (* Vaclav Kotesovec, Mar 11 2014 *)

E.g.f. satisfies A(x) = A058379(x) - log(1+x).
E.g.f.: -1/2 - log(1+x)/2 - LambertW(-exp(-1/2)*sqrt(1+x)/2). - Vaclav Kotesovec, Mar 11 2014
a(n) ~ n^(n-1) / (2*sqrt(2)*(4-exp(1))^(n-1/2)). - Vaclav Kotesovec, Mar 11 2014

A003431 Number of isomorphism classes of connected irreducible posets with n labeled points.

Original entry on oeis.org

1, 1, 0, 0, 1, 12, 104, 956, 10037, 126578, 1971005, 38569954, 958347642, 30400603560, 1234260982770, 64187360439352, 4275470549123119

Offset: 0

N. J. A. Sloane and Richard Stanley

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

S. R. Finch, Series-parallel networks
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for sequences related to posets

Cf. A003430, A046906.

More terms from Richard Stanley, Jun 19 2003
2 more terms from Vladeta Jovovic, Feb 17 2008
Title clarified by Geoffrey Critzer, Jul 08 2022
a(0) changed to 1 by Geoffrey Critzer, Jul 10 2022

A006349 Related to series-parallel networks.

Original entry on oeis.org

1, 5, 13, 45, 121, 413, 1261, 4221, 13801, 46365, 155497, 527613, 1792805, 6126293, 20986153, 72121853, 248396793, 857416949, 2964896877, 10269596445, 35622421561, 123728022269, 430254861945, 1497796774077, 5219231003621

Offset: 1

N. J. A. Sloane

nonn

Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A000084, A006350, A058351, A058352, A058353, A000669.

A058352(n) + n*A000084(n).

A006350 Related to series-parallel networks.

Original entry on oeis.org

0, 1, 7, 27, 101, 337, 1151, 3843, 12965, 43773, 148529, 505605, 1727771, 5920823, 20345445, 70073901, 241849929, 836230109, 2896104951, 10044664507, 34884102385, 121293088909, 422196245641, 1471030361069, 5130057477187, 17905427995239

Offset: 1

N. J. A. Sloane

Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A000084, A006349, A058351, A058352, A058353, A000669.

Sum_{k=1..n-1} A000084(k)*A006349(n-k), n >= 2.

A058387 Number of series-parallel networks with n unlabeled edges, multiple edges not allowed.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 18, 40, 94, 224, 548, 1356, 3418, 8692, 22352, 57932, 151312, 397628, 1050992, 2791516, 7447972, 19950628, 53635310, 144664640, 391358274, 1061628772, 2887113478, 7869761108, 21497678430, 58841838912, 161356288874

Offset: 0

N. J. A. Sloane, Dec 20 2000

This is a series-parallel network: o-o; all other series-parallel networks are obtained by connecting two series-parallel networks in series or in parallel. See A000084 for examples.

Order is not considered significant in series configurations. - Andrew Howroyd, Dec 22 2020

			From _Andrew Howroyd_, Dec 22 2020: (Start)
In the following examples, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element (an edge) is denoted by 'o'.
a(1) = 1: (o).
a(2) = 1: (oo).
a(3) = 2: (ooo), (o|oo).
a(4) = 4: (oooo), (o(o|oo)), (o|ooo), (oo|oo).
a(5) = 8: (ooooo), (oo(o|oo)), (o(o|ooo)), (o(oo|oo)), (o|oooo), (o|o(o|oo)),  (oo|ooo), (o|oo|oo).
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..500
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the sequence v_n).
Index entries for sequences mentioned in Moon (1987)

A000084 is the case that multiple edges are allowed.
A058381 is the case that edges are labeled.
A339290 is the case that order is significant in series configurations.
Cf. A058385, A058386, A000311, A000669, A006351.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(s=p=vector(n)); p[1]=1; for(n=2, n, s[n]=EulerT(p[1..n])[n]; p[n]=vecsum(EulerT(s[1..n])[n-1..n])-s[n]); concat([0], p+s)} \\ Andrew Howroyd, Dec 22 2020

a(n) = A058385(n) + A058386(n).

A058540 Another 3-way generalization of series-parallel networks with n unlabeled edges.

Original entry on oeis.org

0, 1, 3, 9, 36, 144, 651, 3015, 14634, 72654, 369063, 1904985, 9971889, 52788393, 282161025, 1520597895, 8253281871, 45075359277, 247534382298, 1365994896264, 7571065357620, 42127865408028, 235246997219400, 1317894484506336

Offset: 0

N. J. A. Sloane, Dec 24 2000

nonn

Compare the combstruct construction here with those for A000084 and A058534.

Cf. A000084, A058534, A058371.

spec := [ N, {N=Union(Z,S,P,Q), S=Set(Union(Z,P,Q),card>=2), P=Set(Union(Z,S,Q),card>=2), Q=Set(Union(Z,S,P),card>=2)} ]; [seq(combstruct[count](spec,size=n), n=0..40)]; # N=A058540, S=A058371

A058385 Number of essentially parallel series-parallel networks with n unlabeled edges, multiple edges not allowed.

Original entry on oeis.org

0, 1, 0, 1, 2, 4, 9, 20, 47, 112, 274, 678, 1709, 4346, 11176, 28966, 75656, 198814, 525496, 1395758, 3723986, 9975314, 26817655, 72332320, 195679137, 530814386, 1443556739, 3934880554, 10748839215, 29420919456, 80678144437, 221618678694

Offset: 0

N. J. A. Sloane, Dec 20 2000

Vaclav Kotesovec, Table of n, a(n) for n = 0..500 (using data from A058387)
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Ji Li, Combinatorial Logarithm and Point-Determining Cographs, Electronic Journal of Combinatorics, 19 (3) (2012), #P8.
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the sequence q_n).
Wei Wang and Ximei Huang, Almost all cographs have a cospectral mate, arXiv:2507.16730 [math.CO], 2025. See p. 6.
Index entries for sequences mentioned in Moon (1987)

Cf. A058379, A058386, A058387.

Q := x; q[1] := 1; for d from 1 to 40 do q[d+1] := c; Q := Q+c*x^(d+1); t0 := mul((1-x^j)^(-q[j]),j=1..d+1); t01 := series(t0,x,d+2); t05 := series(2*Q +1-x+x^2 -t01, x, d+2); t1 := coeff(t05,x,d+1); t2 := solve(t1,c); q[d+1] := t2; Q := subs(c=t2,Q); Q := series(Q,x,d+2); od: A058385 := n->coeff(Q,x,n);

max = 31; f[x_] := Sum[a[k]*x^k, {k, 0, max}]; a[0] = 0; a[1] = 1; a[2] = 0; a[3] = 1; se = Series[ 1 - x + x^2 + 2*f[x] - Product[(1 - x^j)^(-a[j]), {j, 1, max}], {x, 0, max}]; sol = Solve[ Thread[ CoefficientList[ se, x] == 0]]; A058385 = Table[a[n], {n, 0, max}] /. First[sol] (* Jean-François Alcover, Dec 27 2011, after g.f. *)
terms = 32; A[] = 0; Do[A[x] = (1/2)*(-1 + x - x^2 + Product[(1 - x^j)^(-Ceiling[Coefficient[A[x], x, j]]), {j, 1,  terms}]) + O[x]^ terms // Normal, 4*terms]; CoefficientList[A[x] + O[x]^terms, x] (* Jean-François Alcover, Jan 10 2018 *)

G.f. satisfies 1 - x + x^2 + 2*A(x) = Product_{j>=1} (1-x^j)^(-a(j)).

A058534 A 3-way generalization of series-parallel networks with n unlabeled edges.

Original entry on oeis.org

0, 1, 3, 6, 15, 36, 99, 270, 783, 2298, 6936, 21204, 65895, 206862, 656253, 2098602, 6761028, 21917364, 71450229, 234070806, 770216253, 2544458592, 8435990916, 28060099692, 93612265143, 313153860210, 1050194570445, 3530080085868

Offset: 0

N. J. A. Sloane, Dec 24 2000

nonn

Compare the combstruct construction here with that for A000084.

Cf. A000084, A058540, A000669, A058561.

spec := [ N, {N=Union(Z,S,P,Q), S=Set(Union(Z,P),card>=2), P=Set(Union(Z,Q),card>=2), Q=Set(Union(Z,S),card>=2)} ]; [seq(combstruct[count](spec,size=n), n=0..40)]; # N = A058534, S=A000669

A363065 Number of Laplacian integral graphs on n vertices.

Original entry on oeis.org

1, 2, 4, 10, 24, 70, 188, 553, 1721, 5716

Offset: 1

Nathaniel Johnston, May 16 2023

A (simple, undirected) graph is called Laplacian integral if all eigenvalues of its Laplacian matrix are integers. The corresponding sequence that uses the adjacency matrix instead of the Laplacian matrix is A077027.

Since every cograph is Laplacian integral, a(n) >= A000084(n).

			For n <= 3, all graphs are Laplacian integral, so a(n) = A000088(n) when n <= 3.
There is exactly one graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix
   1 -1  0  0
  -1  2 -1  0
   0 -1  2 -1
   0  0 -1  1
which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.

R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.

Cf. A000084, A000088, A077027, A363064 (connected graphs only).

a(10) from M. A. Achterberg, May 26 2023

cp's OEIS Frontend

A058381 Number of series-parallel networks with n labeled edges, multiple edges not allowed.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A003431 Number of isomorphism classes of connected irreducible posets with n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A006349 Related to series-parallel networks.

Views

Author

Keywords

References

Crossrefs

Formula

A006350 Related to series-parallel networks.

Views

Author

Keywords

References

Crossrefs

Formula

A058387 Number of series-parallel networks with n unlabeled edges, multiple edges not allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A058540 Another 3-way generalization of series-parallel networks with n unlabeled edges.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A058385 Number of essentially parallel series-parallel networks with n unlabeled edges, multiple edges not allowed.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A058534 A 3-way generalization of series-parallel networks with n unlabeled edges.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A363065 Number of Laplacian integral graphs on n vertices.