%I A007889
%S A007889 1,1,2,7,36,246,2104,21652,260720,3598120,56010096,971055240,18558391936,
%T A007889 387665694976,8787898861568,214868401724416,5636819806209792,
%U A007889 157935254554567296,4707152127520549120,148704074888134683520
%N A007889 Number of intransitive (or alternating) trees: vertices are [0,n] and 
               for no i<j<k are both (i,j) and (j,k) edges.
%C A007889 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 (deutsch(AT)duke.poly.edu), 
               Nov 24 2004
%D A007889 C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees, 
               J. Combin. Theory Ser. A 94 (2001), 142-151.
%D A007889 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, Birkhauser, 1997.
%D A007889 A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 
               360-366.
%D A007889 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Problem 5.41(a).
%H A007889 A. Postnikov, <a href="http://www-math.mit.edu/~apost/papers/index.html">
               home page</a>
%H A007889 <a href="Sindx_Tra.html#trees">Index entries for sequences related to 
               trees</a>
%F A007889 E.g.f. 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 (pauldhanna(AT)juno.com), 
               Mar 29 2008
%F A007889 E.g.f.: -2/x*LambertW(-1/2*x*exp(1/2*x)). - Vladeta Jovovic (vladeta(AT)eunet.rs), 
               Mar 29 2008
%F A007889 Comments 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).
%F A007889 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)
%p A007889 f := (n)->1/(2^n*(n+1))*sum(binomial(n+1,k)*k^n,'k'=1..(n+1));
%o A007889 (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 (pauldhanna(AT)juno.com), Mar 29 2008
%o A007889 (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
%Y A007889 Cf. A038049.
%Y A007889 Cf. A138860.
%Y A007889 Sequence in context: A095793 A029768 A167199 this_sequence A125033 A034430 
               A143805
%Y A007889 Adjacent sequences: A007886 A007887 A007888 this_sequence A007890 A007891 
               A007892
%K A007889 nonn,easy,nice
%O A007889 0,3
%A A007889 Alexander Postnikov [ apost(AT)math.mit.edu ]