A007889 Number of intransitive (or alternating, or Stanley) trees: vertices are [0,n] and for no i<j<k are both (i,j) and (j,k) edges.

1, 1, 2, 7, 36, 246, 2104, 21652, 260720, 3598120, 56010096, 971055240, 18558391936, 387665694976, 8787898861568, 214868401724416, 5636819806209792, 157935254554567296, 4707152127520549120, 148704074888134683520, 4963548160096887021056, 174553183413968718996736

Offset

0,3

Comments

Number of local binary search trees (i.e. labeled binary trees such that every left child has a smaller label than its parent and every right child has a larger label than its parent) on n vertices. Example: a(3)=7 because we have 3L2L1, 2L1R3, 3L1R2, 1R2R3, 1R3L2, 2R3L1 (Li means left child labeled i, RI means right child labeled i) and root 2 with left child 1 and right child 3. - Emeric Deutsch, Nov 24 2004

Number of regions of the Linial arrangement. - Ira M. Gessel, Nov 01 2023

References

I. M. Gelfand, M. I. Graev and A. Postnikov, Combinatorics of hypergeometric functions associated with positive roots, in Arnold-Gelfand Mathematical Seminars: Geometry and Singularity Theory, Birkhäuser, 1997.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.41(a).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees, J. Combin. Theory Ser. A 94 (2001), 142-151.

Sergey Fomin and Grigory Mikhalkin, Labeled floor diagrams for plane curves, arXiv:0906.3828, 2009-2010. [N. J. A. Sloane, Sep 27 2010]

G. Hetyei, Efron's coins and the Linial arrangement, arXiv preprint arXiv:1511.04482 [math.CO], 2015.

D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]

A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.

Richard P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. USA 93 (1996), 2620-2625.

Index entries for sequences related to trees

Formula

a(n) = (1/((n+1)*2^n))*Sum_{k=1..n+1} C(n+1,k)*k^n.

E.g.f. A(x) satisfies: A(x) = exp( x*(1 + A(x))/2 ). E.g.f. A(x) equals the inverse function of 2*log(x)/(1+x). - Paul D. Hanna, Mar 29 2008

E.g.f.: -2/x*LambertW(-1/2*x*exp(1/2*x)). - Vladeta Jovovic, Mar 29 2008

From Vladeta Jovovic and Paul D. Hanna, Apr 03 2008: (Start)

Powers of e.g.f.: If A(x)^p = Sum_{n>=0} a(n,p)*x^n/n! then a(n,p) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*p*(k+p)^(n-1).

Let A(x) = e.g.f. of A007889, B(x) = e.g.f. of A138860 where B(x) = exp( x*[B(x) + B(x)^2]/2 ); then B(x) = A(x*B(x)) = (1/x)*Series_Reversion(x/A(x)) and A(x) = B(x/A(x)) = x/Series_Reversion(x*B(x)). (End)

For n>=2, a(n)=Sum_{1,...,floor(n/2)}binomial(n-1, 2k-1)*k^(n-2). [Vladimir Shevelev, Mar 21 2010]

For n>0, a(n) = A088789(n+1)*2/(n+1). [Vaclav Kotesovec, Dec 26 2011]

Maple

f:= n->1/(2^n*(n+1))*add(binomial(n+1, k)*k^n, k=1..(n+1)): seq(f(n), n=0..19);

Mathematica

With[{nn=20}, CoefficientList[Series[-2/x LambertW[-1/2x Exp[x/2]], {x, 0, nn}], x]Range[0, nn]!] (* Harvey P. Dale, Aug 12 2011 *)
Table[1/((n+1)2^n) Sum[Binomial[n+1, k]k^n, {k, n+1}], {n, 0, 20}] (* Harvey P. Dale, Apr 21 2012 *)

Prog

(PARI) {a(n)=local(A=1+x); for(i=0, n, A=exp(x*(1+A)/2 +x*O(x^n))); n!*polcoeff(A, n)} \\ Paul D. Hanna, Mar 29 2008
(PARI) /* Coefficients of A(x)^p are given by: */ {a(n, p=1)=(1/2^n)*sum(k=0, n, binomial(n, k)*p*(k+p)^(n-1))} \\ Vladeta Jovovic and Paul D. Hanna, Apr 03 2008
(Sage)
def A007889(n) : return add(binomial(n, k)*(k+1)^(n-1) for k in (0..n))/2^n
for n in (0..19) : print(A007889(n)) # Peter Luschny, Feb 29 2012

Crossrefs

Cf. A038049, A138860, A283828, A323841.

Row sums of A029847.

Sequence in context: A029768 A180271 A167199 * A125033 A034430 A143805

Adjacent sequences: A007886 A007887 A007888 * A007890 A007891 A007892

Keyword

nonn,easy,nice

Author

Alexander Postnikov [ apost(AT)math.mit.edu ]

Status

approved