login
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.
18

%I #76 Nov 06 2023 07:17:54

%S 1,1,2,7,36,246,2104,21652,260720,3598120,56010096,971055240,

%T 18558391936,387665694976,8787898861568,214868401724416,

%U 5636819806209792,157935254554567296,4707152127520549120,148704074888134683520,4963548160096887021056,174553183413968718996736

%N 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.

%C 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

%C Number of regions of the Linial arrangement. - _Ira M. Gessel_, Nov 01 2023

%D 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.

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

%H Vincenzo Librandi, <a href="/A007889/b007889.txt">Table of n, a(n) for n = 0..200</a>

%H C. Chauve, S. Dulucq and A. Rechnitzer, <a href="https://doi.org/10.1006/jcta.2000.3121">Enumerating alternating trees</a>, J. Combin. Theory Ser. A 94 (2001), 142-151.

%H Sergey Fomin and Grigory Mikhalkin, <a href="http://arxiv.org/abs/0906.3828">Labeled floor diagrams for plane curves</a>, arXiv:0906.3828, 2009-2010. [_N. J. A. Sloane_, Sep 27 2010]

%H G. Hetyei, <a href="http://arxiv.org/abs/1511.04482">Efron's coins and the Linial arrangement</a>, arXiv preprint arXiv:1511.04482 [math.CO], 2015.

%H D. E. Knuth, <a href="/A323841/a323841.pdf">Letter to Daniel Ullman and others</a>, Apr 29 1997 [Annotated scanned copy, with permission]

%H A. Postnikov, <a href="https://doi.org/10.1006/jcta.1996.2735">Intransitive Trees</a>, J. Combin. Theory Ser. A 79 (1997), 360-366.

%H Richard P. Stanley, <a href="https://www.pnas.org/doi/epdf/10.1073/pnas.93.6.2620">Hyperplane arrangements, interval orders, and trees</a>, Proc. Natl. Acad. Sci. USA 93 (1996), 2620-2625.

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

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

%F 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

%F E.g.f.: -2/x*LambertW(-1/2*x*exp(1/2*x)). - _Vladeta Jovovic_, Mar 29 2008

%F From _Vladeta Jovovic_ and _Paul D. Hanna_, Apr 03 2008: (Start)

%F 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 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)

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

%F For n>0, a(n) = A088789(n+1)*2/(n+1). [_Vaclav Kotesovec_, Dec 26 2011]

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

%t 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 *)

%t 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 *)

%o (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

%o (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

%o (Sage)

%o def A007889(n) : return add(binomial(n,k)*(k+1)^(n-1) for k in (0..n))/2^n

%o for n in (0..19) : print(A007889(n)) # _Peter Luschny_, Feb 29 2012

%Y Cf. A038049, A138860, A283828, A323841.

%Y Row sums of A029847.

%K nonn,easy,nice

%O 0,3

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