|
| |
|
|
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.
|
|
8
| |
|
|
1, 1, 2, 7, 36, 246, 2104, 21652, 260720, 3598120, 56010096, 971055240, 18558391936, 387665694976, 8787898861568, 214868401724416, 5636819806209792, 157935254554567296, 4707152127520549120, 148704074888134683520
(list; graph; refs; listen; history; internal format)
|
|
|
|
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
|
|
|
REFERENCES
| 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. See Section 7.4. [From N. J. A. Sloane, Sep 27 2010]
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.
A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.41(a).
|
|
|
LINKS
| A. Postnikov, home page
Index entries for sequences related to trees
C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees
|
|
|
FORMULA
| a(n) = 1/((n+1)*2^n)*sum(k=1..n+1, C(n+1,k)*k^n ).
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, Mar 29 2008
E.g.f.: -2/x*LambertW(-1/2*x*exp(1/2*x)). - Vladeta Jovovic (vladeta(AT)eunet.rs), Mar 29 2008
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).
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). [From Vladimir Shevelev, Mar 21 2010]
For n>0, a(n) = A088789(n+1)*2/(n+1). [From Vaclav Kotesovec, Dec 26 2011]
|
|
|
MAPLE
| f := (n)->1/(2^n*(n+1))*sum(binomial(n+1, k)*k^n, 'k'=1..(n+1));
|
|
|
MATHEMATICA
| With[{nn=20}, CoefficientList[Series[-2/x LambertW[-1/2x Exp[x/2]], {x, 0, nn}], x]Range[0, nn]!] (* From Harvey P. Dale, Aug 12 2011 *)
|
|
|
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
|
|
|
CROSSREFS
| Cf. A038049.
Cf. A138860.
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 ]
|
| |
|
|
