A048287 Number of semiorders on n labeled nodes whose incomparability graph is connected.

1, 1, 7, 61, 751, 11821, 226927, 5142061, 134341711, 3975839341, 131463171247, 4803293266861, 192178106208271, 8356430510670061, 392386967808249967, 19788154572706556461, 1066668756919315412431, 61204224384073232815981

Offset

1,3

Links

Robert Israel, Table of n, a(n) for n = 1..373

Mats Granvik, Power series to calculate Lambert W up to infinity

Formula

E.g.f.: 1-2*(1-exp(-x))/(1-sqrt(4*exp(-x)-3)).

E.g.f.: (1 - sqrt(4*exp(-x) - 3)) / 2. - Michael Somos, Nov 26 2017

a(n) = Sum_{k=1..n} (-1)^(n-k)*Stirling2(n, k)*k!*Catalan(k-1). - Vladeta Jovovic, Oct 18 2003

Equals column 1 (unsigned) of triangle A136595, which is the matrix inverse of the triangle A136590 of trinomial logarithmic coefficients. - Paul D. Hanna, Jan 10 2008

E.g.f A(x)=F(exp(x)-1), F(x)=x*A005043(x). - Vladimir Kruchinin, Sep 07 2010

a(n) = (-1)^(n-1) + Sum_{k=1..n-1} binomial(n,k)*a(k)*a(n-k). - Robert Israel, Mar 01 2016

Given e.g.f. =: A(x), then exp(-x) = A(x)^2 - A(x) + 1 = A'(x)*(1 - 2*A(x)). - Michael Somos, Nov 26 2017

a(n) ~ sqrt(3/8) * n^(n-1) / (log(4/3)^(n - 1/2) * exp(n)). - Vaclav Kotesovec, Dec 16 2020

Example

a(3)=7, the seven semiorders being three disjoint points and the disjoint union of a point and a two-element chain (with six labelings).

Maple

A048287 := n -> add((-1)^(n-k-1)*Stirling2(n, k+1)*(2*k)!/k!, k=0..n-1):
seq(A048287(n), n=1..18); # Peter Luschny, Jan 27 2016

Mathematica

Table[Sum[(-1)^(n - k) StirlingS2[n, k] k!*CatalanNumber[k - 1], {k, n}], {n, 20}] (* Michael De Vlieger, Jan 27 2016 *)
Rest[Range[0, 18]! CoefficientList[Series[1 - 2 (1 - Exp[-x]) /(1 - Sqrt[4 Exp[-x] - 3]), {x, 0, 18}], x]] (* Vincenzo Librandi, Jan 28 2016 *)

Prog

(PARI) {a(n)=local(A136590=matrix(n+1, n+1, r, c, if(r>=c, (r-1)!/(c-1)!*polcoeff(log(1+x+x^2 +x*O(x^n))^(c-1), r-1)))); (-1)^(n+1)*(A136590^-1)[n+1, 2]} \\ Paul D. Hanna, Jan 10 2008
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( (1 - sqrt(4*exp(-x + x*O(x^n)) - 3)) / 2, n))}; /* Michael Somos, Nov 26 2017 */
(PARI) {a(n) = if( n<1, 0, n! * polcoeff( serreverse( -log(1 - x + x^2 + x * O(x^n))), n))}; /* Michael Somos, Nov 26 2017 */

Crossrefs

Cf. A000108, A006531.

Cf. A136595, A136590.

Sequence in context: A261901 A368324 A350157 * A317430 A145507 A254121

Adjacent sequences: A048284 A048285 A048286 * A048288 A048289 A048290

Keyword

easy,nonn

Author

Richard Stanley

Extensions

More terms from Vladeta Jovovic, Oct 18 2003

Status

approved