A058349 Number of connected labeled series-parallel posets on n nodes.

1, 2, 12, 122, 1740, 31922, 715932, 18978122, 580513260, 20125554242, 779832497532, 33398722757402, 1566656717322060, 79879485803841362, 4398701789915269212, 260166428897541369962, 16449181879032096013740, 1107112451498156565581282, 79030557433744270179981372

Offset

1,2

Comments

Also, number of labeled blobs with n edges.

References

R. C. Read, Graphical enumeration by cycle-index sums: first steps toward a unified treatment, preprint, Sept. 26, 1991.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.39, page 133, g(n).

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Natalia L. Skirrow, proof of double-sum formula

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

Index entries for sequences related to posets

Formula

Read (1991) reference gives generating functions (see PARI code for one example).

A048172(n) = a(n)+A048174(n), n>1.

a(n) = (n-1)!*sum(k=1..n-1, binomial(n+k-1,n-1)*sum(j=1..k, binomial(k,j)*((sum(l=0..j-1, (binomial(j,l)*((-1)^(n-l+j-1)+1)*sum(r=1..j-l, binomial(j-l,r)*2^(j-l-r-1)*(-1)^(r-j)*sum(i=0..r, (r-2*i)^(n-l+j-1)*binomial(r,i))))/(n-l+j-1)!))))), n>1, a(1)=1. - Vladimir Kruchinin, Feb 19 2012

a(n) ~ n^(n-1) / (5^(1/4)*exp(n)*(2-sqrt(5)+log((1+sqrt(5))/2))^(n-1/2)). - Vaclav Kotesovec, Mar 09 2014

a(n+1) = Sum_{i=0..n} ( Sum_{d=-i..i} binomial(2*i,i+d)*d^(i+n)*(-1)^(n-d) )/i! (see link for proof). - Natalia L. Skirrow, Nov 16 2025

Maple

# continue from A053554
t1 := log(1+EGF053554): t2 := series(t1, x, 30); SERIESTOLISTMULT(t2);

Mathematica

Drop[ CoefficientList[ InverseSeries[ Series[x + 2*(1 - Cosh[x]) , {x, 0, 19}], y], y], 1]* Range[19]! (* Jean-François Alcover, Sep 21 2011, after g.f. *)

Prog

(PARI) my(x='x+O('x^20), t=x+2*(1-cosh(x))); Vec(serlaplace(serreverse(t))) \\ Joerg Arndt, Feb 04 2011
(PARI) \\ using function inverse_bell_matrix_row from A354794
a(n) = inverse_bell_matrix_row(n, x->-(x%2)<<1)[1] \\ Mikhail Kurkov, May 11 2026
(Maxima) a(n):=if n=1 then 1 else (n-1)!*sum(binomial(n+k-1, n-1)*sum(binomial(k, j)*((sum((binomial(j, l)*((-1)^(n-l+j-1)+1)*sum(binomial(j-l, r)*2^(j-l-r-1)*(-1)^(r-j)*sum((r-2*i)^(n-l+j-1)*binomial(r, i), i, 0, r), r, 1, j-l))/(n-l+j-1)!, l, 0, j-1))), j, 1, k), k, 1, n-1); /* Vladimir Kruchinin, Feb 19 2012 */
(SageMath)
R.<x> = PowerSeriesRing(QQ, default_prec=20)
t = x + 2*(1 - (x.cosh()))
u = t.reverse()
print([u[n] * factorial(n) for n in range(1, u.prec())]) # Peter Luschny, Nov 16 2025
(Python)
def A058349(n: int) -> int:
    """ Also defined for n = 0 and returns 0 in that case. """
    ret, fact = 0, 1
    s = -1 if (n - 1) % 2 else 1
    for i in range(n):
        S, c = 0, 1
        b = i + n - 1
        for k in range(2*i + 1):
            d = k - i
            if d == 0: p = 0 if b > 0 else 1
            else: p = d ** b
            S += c * p * (s * (-1 if d % 2 else 1))
            if k < 2*i: c = c * (2*i - k) // (k + 1)
        fact = fact * i if i > 0 else 1
        ret += S // fact
    return ret
print([A058349(n) for n in range(1, 20)])  # Peter Luschny, Mar 29 2026

Crossrefs

A053554(n) = a(n) + A058350(n) (n>=2).

Sequence in context: A034524 A051782 A048173 * A375897 A013469 A372178

Adjacent sequences: A058346 A058347 A058348 * A058350 A058351 A058352

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Dec 16 2000

Extensions

More terms from Joerg Arndt, Feb 04 2011

Status

approved