A003430 -id:A003430 - cp's OEIS frontend

A339225 Number of unoriented series-parallel networks with n elements.

1, 2, 4, 11, 30, 98, 328, 1193, 4459, 17287, 68283, 274726, 1118960, 4607578, 19135274, 80063095, 337104367, 1427274619, 6072510001, 25949049372, 111319539096, 479243000380, 2069825207344, 8965693829582, 38940393808337, 169546919220357, 739895248735963

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

A series configuration is the unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is the unit element or a multiset of two or more series configurations. a(n) is the number of distinct series or parallel configurations with n unit elements modulo reversing the order of all series configurations.

			In the following examples of series-parallel networks, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(2) = 2: (oo), (o|o).
a(3) = 4: (ooo), (o(o|o)), (o|o|o), (o|oo).
a(4) = 11: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)),  (o|o|o|o), (o|o|oo), (oo|oo), (o|ooo), (o|o(o|o)).

Cf. A000084, A003430 (oriented), A339159 (achiral), A339223, A339224.

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2), t=p); for(n=1, n\2, t=x + q*(1 + p); p=x + x*Ser(EulerT(Vec(t+(s-subst(t,x,x^2))/2))) - t); Vec(p+t-x+B(n))/2}

a(n) = (A003430(n) + A339159(n))/2.
a(n) = A339223(n) + A339224(n) for n > 1.
A000084(n) <= a(n) <= A003430(n).

A339290 Number of oriented series-parallel networks with n elements and without multiple unit elements in parallel.

Original entry on oeis.org

1, 1, 2, 5, 13, 36, 103, 306, 930, 2887, 9100, 29082, 93951, 306414, 1007361, 3335088, 11108986, 37203873, 125193694, 423099557, 1435427202, 4886975378, 16690971648, 57172387872, 196358421066, 676050576441, 2332887221847, 8067160995797, 27950871439353, 97019613539949

Offset: 1

Andrew Howroyd, Dec 07 2020

nonn

A series configuration is an ordered concatenation of two or more parallel configurations and a parallel configuration is a multiset of two or more unit elements or series configurations. In this variation, parallel configurations may include the unit element only once. a(n) is the total number of series and parallel configurations with n unit elements.

			In the following examples, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(2) = 1: (oo).
a(3) = 2: (ooo), (o|oo).
a(4) = 5: (oooo), (o(o|oo)), ((o|oo)o), (o|ooo), (oo|oo).
a(5) = 13: (ooooo), (oo(o|oo)), (o(o|oo)o), ((o|oo)oo), (o(o|ooo)), (o(oo|oo)), ((o|ooo)o), ((oo|oo)o), (o|oooo), (o|o(o|oo)), (o|(o|oo)o), (oo|ooo), (o|oo|oo).

Andrew Howroyd, Table of n, a(n) for n = 1..500

A003430 is the case with multiple unit elements in parallel allowed.
A058387 is the case that order is not significant in series configurations.
Cf. A339156, A339288, A339289, A339293 (achiral), A339296 (unoriented), A339301 (labeled).

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n, Z=x)={my(p=Z+O(x^2)); for(n=2, n, p = Z + (1 + Z)*x*Ser(EulerT( Vec(p^2/(1+p), -n) ))); Vec(p)}

a(n) = A339288(n) + A339289(n).

G.f.: P(x)/(1 - P(x)) where P(x) is the g.f. of A339289.

A007453 Number of unlabeled connected series-parallel posets with n nodes.

Original entry on oeis.org

1, 1, 3, 9, 30, 103, 375, 1400, 5380, 21073, 83950, 338878, 1383576, 5702485, 23696081, 99163323, 417553252, 1767827220, 7520966100, 32135955585, 137849390424, 593407692685, 2562695780058, 11099806544050, 48206136562750, 209876865026303, 915840095739301

Offset: 1

N. J. A. Sloane, Mira Bernstein

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 100 terms from Jean-François Alcover)
B. I. Bayoumi, M. H. El-Zahar and S. M. Khamis, Asymptotic enumeration of N-free partial orders, Order 6 (1989), 219-232.
P. J. Cameron, On the probability of connectedness, Discrete Math., 167 (1997), 175-187.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.
Index entries for sequences related to posets

Cf. A003430, A007454.

terms = 25; A[_] = 1;
Do[A[x_] = Exp[Sum[(1/k)*(A[x^k] + 1/A[x^k] - 2 + x^k), {k, 1, terms+1}]] + O[x]^(terms+1) // Normal, terms+1];
A003430 = CoefficientList[A[x], x] // Rest;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i-1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
EULERi[A003430] (* Jean-François Alcover, Jan 23 2020 *)

See the 1989 and 1997 papers by Cameron cited above for generating functions, and the 1997 paper for asymptotics.
Inverse Euler transform of A003430. - Sean A. Irvine, Jan 04 2018
a(n) = A003430(n) - A007454(n) for n > 1. - Sean A. Irvine, Jan 04 2018

Name corrected by Salah Uddin Mohammad, Jun 07 2020

A339228 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks with n colored elements using exactly k colors.

Original entry on oeis.org

1, 2, 3, 5, 22, 19, 15, 146, 321, 195, 48, 970, 4116, 5972, 2791, 167, 6601, 48245, 125778, 135235, 51303, 602, 46012, 546570, 2281528, 4238415, 3609966, 1152019, 2256, 328188, 6118320, 38437972, 109815445, 157612413, 111006329, 30564075

Offset: 1

Andrew Howroyd, Nov 28 2020

A series configuration is a unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is a unit element or a multiset of two or more series configurations. T(n, k) is the number of series or parallel configurations with n unit elements of k colors using each color at least once.

			Triangle begins:
    1;
    2,     3;
    5,    22,     19;
   15,   146,    321,     195;
   48,   970,   4116,    5972,    2791;
  167,  6601,  48245,  125778,  135235,   51303;
  602, 46012, 546570, 2281528, 4238415, 3609966, 1152019;
  ...

Columns 1..2 are A003430, A339227.
Row sums are A339229.
Main diagonal is A048172.
Cf. A339226, A339228.

\\ R(n,k) gives colorings using at most k colors as a vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(Z=k*x, p=Z+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+Z)))); Vec(p)}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(8)); for(n=1, #T~, print(T[n, 1..n]))}

A048172 Number of labeled series-parallel graphs with n edges.

Original entry on oeis.org

1, 3, 19, 195, 2791, 51303, 1152019, 30564075, 935494831, 32447734143, 1257770533339, 53884306900515, 2528224238464471, 128934398091500823, 7101273378743303779, 420078397130637237915, 26563302733186339752511, 1788055775343964413724143, 127652707703771090396080939

Offset: 1

N. J. A. Sloane

Labeled N-free posets. - Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002

Ronald C. Read, Graphical enumeration by cycle-index sums: first steps toward a unified treatment, Research Report CORR 91-19, University of Waterloo, Sept 1991.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.39.

Vincenzo Librandi, Table of n, a(n) for n = 1..100
F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
Frédéric Fauvet, L. Foissy, D. Manchon, Operads of finite posets, arXiv preprint arXiv:1604.08149 [math.CO], 2016.
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299
Index entries for reversions of series
Index entries for sequences related to posets

Cf. A048174, A058349, A058350.

Cf. A000112 (unlabeled posets), A001035 (labeled posets), A003430 (unlabeled analog).

with(gfun):
f := series((ln(1+x)-x^2/(1+x)), x, 21):
egf := seriestoseries(f, 'revogf'):
seriestolist(egf, 'Laplace');

lim = 19; Join[{1}, Drop[ CoefficientList[ InverseSeries[ Series[x + 2*(1 - Cosh[x]) , {x, 0, lim}], y] + InverseSeries[ Series[-Log[1 - x] - x^2/(1 - x),{x, 0, lim}], y], y], 2]*Range[2, lim]!] (* Jean-François Alcover, Sep 21 2011, after g.f. *)
m = 17; Rest[CoefficientList[InverseSeries[Series[Log[1+x]-x^2/(1+x), {x, 0, m}], x], x]*Table[k!,{k, 0, m}]](* Jean-François Alcover, Apr 18 2011 *)

h(n,k):=if n=k then 0 else (-1)^(n-k)*binomial(n-k-1,k-1); a(n):=if n=1 then 1 else -sum((k!/n!*stirling1(n,k)+sum(binomial(k,j)*sum((j)!/(i)!*stirling1(i,j)*h(n-i,k-j),i,j,n-k+j),j,1,k-1)+h(n,k))*a(k),k,1,n-1); /* Vladimir Kruchinin, Sep 08 2010 */

x='x+O('x^55);
s=-log(1-x)-x^2/(1-x);
A048174=Vec(serlaplace(serreverse(s)));
t=x+2*(1-cosh(x));
A058349=Vec(serlaplace(serreverse(t)));
A048172=A048174+A058349;  A048172[1]-=1;
A048172 /* Joerg Arndt, Feb 04 2011 */

a(n) = A058349(n) + A048174(n).
a(n) = A058349(n) + A058350(n) (n>=2).
Reference (by Ronald C. Read) gives generating functions.
E.g.f. is reversion of log(1+x)-x^2/(1+x).
a(n)=if n=1 then 1 else -sum((k!/n!*stirling1(n,k)+sum(binomial(k,j)*sum((j)!/(i)!*stirling1(i,j)*h(n-i,k-j),i,j,n-k+j),j,1,k-1)+h(n,k))*a(k),k,1,n-1), h(n,k)=if n=k then 0 else (-1)^(n-k)*binomial(n-k-1,k-1), n>0. - Vladimir Kruchinin, Sep 08 2010
a(n) ~ sqrt((5+3*sqrt(5))/10) * n^(n-1) / (exp(n) * (2 - sqrt(5) + log((1+sqrt(5))/2))^(n-1/2)). - Vaclav Kotesovec, Feb 25 2014

More terms from Joerg Arndt, Feb 04 2011

A007454 Number of unlabeled disconnected series-parallel posets with n nodes.

Original entry on oeis.org

1, 1, 2, 6, 18, 64, 227, 856, 3280, 12885, 51342, 207544, 847886, 3497384, 14541132, 60884173, 256480895, 1086310549, 4623128656, 19759964149, 84784735379, 365066645854, 1576927900803, 6831518134251, 29674505668536, 129216630647787, 563949605921815

Offset: 1

N. J. A. Sloane, Mira Bernstein

nonn

a(1) = 0 would make more sense, but original article has a(1) = 1. - Sean A. Irvine, Jan 04 2018

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 100 terms from Jean-François Alcover)
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Index entries for sequences related to posets

Cf. A003430, A007453.

terms = 25; A[_] = 1;
Do[A[x_] = Exp[Sum[(1/k)*(A[x^k] + 1/A[x^k] - 2 + x^k), {k, 1, terms + 1}]] + O[x]^(terms + 1) // Normal, terms + 1];
A003430 = CoefficientList[A[x], x] // Rest;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
Join[{1}, Rest[A003430 - EULERi[A003430]]] (* Jean-François Alcover, Jan 23 2020 *)

a(n) = A003430(n) - A007453(n) for n > 1. - Sean A. Irvine, Jan 04 2018

Name corrected by Salah Uddin Mohammad, Jun 07 2020

A339157 Number of essentially series achiral series-parallel networks with n elements.

Original entry on oeis.org

1, 1, 1, 3, 4, 11, 17, 46, 78, 203, 372, 946, 1830, 4561, 9207, 22609, 47166, 114514, 245154, 590345, 1289950, 3087959, 6858746, 16352074, 36800928, 87502317, 199036637, 472483088, 1084108363, 2571356964, 5942191918, 14090541799, 32754720101, 77684033014, 181473276607

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

A series configuration is the unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is the unit element or a multiset of two or more series configurations. a(n) is the number of series configurations with n unit elements that are invariant under the reversal of all contained series configurations.

			In the following examples of series-parallel networks, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(2) = 1: (oo).
a(3) = 1: (ooo).
a(4) = 3: (oooo), ((o|o)(o|o)), (o(o|o)o).
a(5) = 4: (ooooo), ((o|o)o(o|o)), (o(o|oo)o), (o(o|o|o)o).
a(6) = 11: (oooooo), ((o|o)oo(o|o)), (o(o|o)(o|o)o), ((o|oo)(o|oo)), ((o|o|o)(o|o|o)), (oo(o|o)oo), ((o|o)(o|o)(o|o)), (o(o|ooo)o), (o(oo|oo)o), (o(o|o|oo)o), (o(o|o|o|o)o).

Cf. A003430, A007453 (oriented), A339158, A339159, A339223 (unoriented).

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2)); for(n=1, n\2, p = x + q*(1 + x + x*Ser(EulerT(Vec(p+(s-subst(p,x,x^2))/2))) - p)); Vec(p+O(x*x^n))}

G.f.: x + (1 + P(x))*B(x^2) where P(x) is the g.f. of A339158 and B(x) is the g.f. of A003430.

A339159 Number of achiral series-parallel networks with n elements.

Original entry on oeis.org

1, 2, 3, 7, 12, 29, 54, 130, 258, 616, 1274, 3030, 6458, 15287, 33335, 78694, 174587, 411469, 925246, 2179010, 4952389, 11662221, 26733827, 62980863, 145385388, 342766624, 795810810, 1878109984, 4381423357, 10352044123, 24247955489, 57362089607

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

A series configuration is the unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is the unit element or a multiset of two or more series configurations. a(n) is the number of series or parallel configurations with n unit elements that are invariant under the reversal of all contained series configurations.

			In the following examples of series-parallel networks, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(2) = 2: (oo), (o|o).
a(3) = 3: (ooo), (o|oo), (o|o|o), (o|ooo), (oo|oo), (o|o|oo), (o|o|o|o).
a(4) = 7: (oooo), ((o|o)(o|o)), (o(o|o)o).

Cf. A003430 (oriented), A339157, A339158, A339225 (unoriented).

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2), t=p); for(n=1, n\2, t=x + q*(1 + p); p=x + x*Ser(EulerT(Vec(t+(s-subst(t,x,x^2))/2))) - t); Vec(p+t-x+O(x*x^n))}

a(n) = A339157(n) + A339158(n) for n > 1.

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

A202180 Number of n-element unlabeled connected N-free posets.

Original entry on oeis.org

1, 1, 3, 9, 31, 115, 474, 2097, 9967, 50315, 268442, 1505463, 8840306, 54169431

Offset: 1

N. J. A. Sloane, Dec 13 2011

Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.

Row sums of A202178 and A202179.

Cf. A003430, A007453, A053554.

Missing term a(12) inserted by Salah Uddin Mohammad, May 26 2020

cp's OEIS Frontend

A339225 Number of unoriented series-parallel networks with n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339290 Number of oriented series-parallel networks with n elements and without multiple unit elements in parallel.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A007453 Number of unlabeled connected series-parallel posets with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339228 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks with n colored elements using exactly k colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A048172 Number of labeled series-parallel graphs with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A007454 Number of unlabeled disconnected series-parallel posets with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339157 Number of essentially series achiral series-parallel networks with n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339159 Number of achiral series-parallel networks with n elements.