|
%I M1476 #77 Dec 02 2020 13:57:16
%S 1,1,2,5,15,48,167,602,2256,8660,33958,135292,546422,2231462,9199869,
%T 38237213,160047496,674034147,2854137769,12144094756,51895919734,
%U 222634125803,958474338539,4139623680861,17931324678301,77880642231286,339093495674090,1479789701661116
%N Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.
%C 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
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.39 (which deals with the labeled case of the same sequence).
%H Alois P. Heinz, <a href="/A003430/b003430.txt">Table of n, a(n) for n = 0..1000</a> (terms n = 1..100 from Jean-François Alcover)
%H B. I. Bayoumi, M. H. El-Zahar and S. M. Khamis, <a href="https://www.researchgate.net/publication/226027783_Asymptotic_enumeration_ofN-free_partial_orders">Asymptotic enumeration of N-free partial orders</a>, Order 6 (1989), 219-232.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H Uli Fahrenberg, Christian Johansen, Georg Struth, Ratan Bahadur Thapa, <a href="https://arxiv.org/abs/1910.06162">Generating Posets Beyond N</a>, arXiv:1910.06162 [cs.FL], 2019.
%H Frédéric Fauvet, L. Foissy, D. Manchon, <a href="https://arxiv.org/abs/1604.08149">Operads of finite posets</a>, arXiv preprint arXiv:1604.08149 [math.CO], 2016.
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Series-parallel networks</a>
%H S. R. Finch, <a href="/A000084/a000084_2.pdf">Series-parallel networks</a>, July 7, 2003. [Cached copy, with permission of the author]
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 72.
%H Soheir M. Khamis, <a href="https://doi.org/10.1016/S0012-365X(03)00106-7">Height counting of unlabeled interval and N-free posets</a>, Discrete Math. 275 (2004), no. 1-3, 165-175.
%H R. P. Stanley, <a href="http://dx.doi.org/10.1090/S0002-9939-1974-0351928-7">Enumeration of posets generated by disjoint unions and ordinal sums</a>, Proc. Amer. Math. Soc. 45 (1974), 295-299. Math. Rev. 50 #4416.
%H R. P. Stanley, <a href="/A003277/a003277.pdf">Letter to N. J. A. Sloane, c. 1991</a>
%H <a href="/index/Pos#posets">Index entries for sequences related to posets</a>
%F 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)).
%F From: _Andrew Howroyd_, Nov 26 2020: (Start)
%F a(n) = A007453(n) + A007454(n) for n > 1.
%F Euler transform of A007453.
%F G.f.: P(x)/(1 - P(x)) where P(x) is the g.f. of A007454.
%F (End)
%e From _Andrew Howroyd_, Nov 26 2020: (Start)
%e 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'.
%e a(1) = 1: (o).
%e a(2) = 2: (oo), (o|o).
%e a(3) = 5: (ooo), (o(o|o)), ((o|o)o), (o|o|o), (o|oo).
%e 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).
%e (End)
%t 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];
%t CoefficientList[A[x], x] // Rest (* _Jean-François Alcover_, Jun 29 2011, updated Jan 12 2018 *)
%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o 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
%Y Row sums of A339231.
%Y Column k=1 of A339228.
%Y Cf. A000084, A003431, A048172 (labeled N-free posets), A007453, A007454, A339156, A339159, A339225.
%K easy,nonn,nice
%O 0,3
%A _N. J. A. Sloane_, _Richard Stanley_, and _Mira Bernstein_
%E Name corrected by _Salah Uddin Mohammad_, Jun 07 2020
%E a(0)=1 prepended (using the g.f.) by _Alois P. Heinz_, Dec 01 2020
|
