A003430 Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes. (Formerly M1476)

1, 1, 2, 5, 15, 48, 167, 602, 2256, 8660, 33958, 135292, 546422, 2231462, 9199869, 38237213, 160047496, 674034147, 2854137769, 12144094756, 51895919734, 222634125803, 958474338539, 4139623680861, 17931324678301, 77880642231286, 339093495674090, 1479789701661116

Offset

0,3

Comments

Number of oriented series-parallel networks with n elements. 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. a(n) is the number of series or parallel configurations with n elements. The sequences A007453 and A007454 enumerate respectively series and parallel configurations. - Andrew Howroyd, Dec 01 2020

References

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.39 (which deals with the labeled case of the same sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 1..100 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, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

Uli Fahrenberg, Christian Johansen, Georg Struth, Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.

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

S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72.

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

R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299. Math. Rev. 50 #4416.

R. P. Stanley, Letter to N. J. A. Sloane, c. 1991

Index entries for sequences related to posets

Formula

G.f. A(x) = 1 + x + 2*x^2 + 5*x^3 + ... satisfies A(x) = exp(Sum_{k>=1} (1/k)*(A(x^k) + 1/A(x^k) - 2 + x^k)).

From: Andrew Howroyd, Nov 26 2020: (Start)

a(n) = A007453(n) + A007454(n) for n > 1.

Euler transform of A007453.

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

(End)

Example

From Andrew Howroyd, Nov 26 2020: (Start)
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) = 5: (ooo), (o(o|o)), ((o|o)o), (o|o|o), (o|oo).
a(4) = 15: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)oo), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)), ((o|oo)o), ((o|o|o)o), (o|o|o|o), (o|o|oo), (oo|oo), (o|ooo), (o|o(o|o)), (o|(o|o)o).
(End)

Mathematica

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];
CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Jun 29 2011, updated Jan 12 2018 *)

Prog

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x, 1-n)))); Vec(p)} \\ Andrew Howroyd, Nov 27 2020

Crossrefs

Row sums of A339231.

Column k=1 of A339228.

Cf. A000084, A003431, A048172 (labeled N-free posets), A007453, A007454, A339156, A339159, A339225.

Sequence in context: A035350 A006570 A149928 * A149929 A337262 A149930

Adjacent sequences: A003427 A003428 A003429 * A003431 A003432 A003433

Keyword

easy,nonn,nice

Author

N. J. A. Sloane, Richard Stanley, and Mira Bernstein

Extensions

Name corrected by Salah Uddin Mohammad, Jun 07 2020

a(0)=1 prepended (using the g.f.) by Alois P. Heinz, Dec 01 2020

Status

approved