login
Number of labeled chains with n edges.
5

%I #38 Mar 11 2014 09:35:12

%S 1,1,7,73,1051,19381,436087,11585953,354981571,12322179901,

%T 477938035807,20485584143113,961567521142411,49054912287659461,

%U 2702571588828034567,159911968233095867953,10114120854154243738771,680943323845807848142861,48622150270026820216099567,3670113810844512283440027673

%N Number of labeled chains with n edges.

%C Number of labeled series-parallel posets on n nodes that are not a nontrivial ordinal sum.

%C Let ( T, < ) and ( U, < ) be posets with T and U disjoint. Their ordinal sum is ( T union U, < ) where x<y if x<y and both in T or both in U, or x in T and y in U. Note ordinal sum is not commutative.

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

%H Vincenzo Librandi, <a href="/A048174/b048174.txt">Table of n, a(n) for n = 1..100</a>

%H Ronald C. Read, <a href="http://www.math.uwaterloo.ca/CandO_Dept/Journals_and_Research/CORR.shtml">Graphical enumeration by cycle-index sums: first steps toward a unified treatment</a>, Research Report CORR 91-19, University of Waterloo, Sept 1991.

%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

%H <a href="/index/Pos#posets">Index entries for sequences related to posets</a>

%F Reference gives generating functions (see PARI code for one example).

%F A048172(n) = A058349(n) + a(n), n>1.

%F A053554(n) = A058349(n) + A058350(n) (n>=2).

%F a(n)=sum(k=1..n-1, (n+k-1)!*sum(j=1..k, (-1)^(j)/(k-j)!*((sum(l=1..j, sum(i=2*l..n+l-1, (binomial(-l+i-1,l-1)*(-1)^(n-i-1)*stirling1(n+j-i-1,j-l))/(l!*(n+j-i-1)!))))+((-1)^(n-1)*stirling1(n+j-1,j))/(n+j-1)!))). - _Vladimir Kruchinin_, Feb 19 2012

%F a(n) ~ (5-sqrt(5)) * n^(n-1) / (2*5^(3/4)*exp(n)*(2-sqrt(5)+log((1+sqrt(5))/2))^(n-1/2)). - _Vaclav Kotesovec_, Mar 09 2014

%p with(gfun): f := series(ln(1+x)-x^2/(1+x), x, 30):

%p egf := seriestoseries(f, 'revogf'):

%p t := series(egf/(1+egf), x, 21):

%p seriestolist(t, 'Laplace');

%t lim = 20; Drop[ CoefficientList[ InverseSeries[ Series[-Log[1 - x] - x^2/(1 - x), {x, 0, lim}], y], y], 1]*Range[lim]! (* _Jean-François Alcover_, Sep 21 2011, after g.f. *)

%t max = 18; S053554 = InverseSeries[ Series[ Log[1+x] - x^2/(1+x), {x, 0, max}], x]; Drop[ CoefficientList[ Series[ S053554 / (1+S053554), {x, 0, max}], x]* Range[0, max]!, 1] (* _Jean-François Alcover_, Nov 29 2011, after Maple *)

%o (Maxima)

%o a(n):=if n=1 then 1 else (sum((n+k-1)!*sum((-1)^(j)/(k-j)!*((sum(sum((binomial(-l+i-1,l-1)*(-1)^(n-i-1)*stirling1(n+j-i-1,j-l))/(l!*(n+j-i-1)!),i,2*l,n+l-1),l,1,j))+((-1)^(n-1)*stirling1(n+j-1,j))/(n+j-1)!),j,1,k),k,1,n-1)); /* _Vladimir Kruchinin_, Feb 19 2012 */

%o (PARI) x='x+O('x^66); s=serreverse(log(1+x)-x^2/(1+x)); Vec(serlaplace(s/(1+s))) \\ _Joerg Arndt_, Mar 11 2014

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _Joerg Arndt_, Feb 04 2011