A100526 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) with n vertices such that the root has only one child.
1, 2, 6, 28, 180, 1476, 14728, 173216, 2346480, 35981200, 616111056, 11652662880, 241259095168, 5427319729664, 131818482923520, 3437894427590656, 95825936705566464, 2842834581982211328, 89435890422890433280, 2974081497762693670400, 104234511362034627442176
Offset: 1
Keywords
Examples
a(3)=6 because we have 3L2L1, 2L1R3, 3L1R2, 1R2R3, 1R3L2, 2R3L1 (Li means left child labeled i, RI means right child labeled i). E.g.f.: A(x) = x + 2*x^2/2! + 6*x^3/3! + 28*x^4/4! + 180*x^5/5! + 1476*x^6/6! +... Given G(x) such that G( sqrt( G(x^2*exp(-x)) ) ) = x, where G(x) = x + 1/2*x^2 + 1/8*x^3 + 1/12*x^4 + 77/384*x^5 + 23/120*x^6 + 2077/46080*x^7 + 179/5040*x^8 + 239525/2064384*x^9 +...+ A273952(n)*x^n/(2^(n-1)*(n-1)!) +... then A(x) = G( sqrt( G(x^2*exp(x)) ) ). - _Paul D. Hanna_, Jun 06 2016
Links
- G. C. Greubel, Table of n, a(n) for n = 1..400
- C. Chauve, S. Dulucq and A. Rechnitzer, Enumerating alternating trees, J. Combin. Theory Ser. A 94 (2001), 142-151.
- A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.
Programs
-
Magma
[2^(1-n)*(&+[ k^(n-1)*Binomial(n, k): k in [1..n]]): n in [1..40]]; // G. C. Greubel, Mar 27 2023
-
Maple
seq((1/2^(n-1))*add(k^(n-1)*binomial(n,k),k=1..n),n=1..22);
-
Mathematica
Rest[CoefficientList[Series[-2*LambertW[-x*E^(x/2)/2], {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Jun 23 2016 *) -
PARI
/* Egf A(x) = G(sqrt(G(x^2*exp(x)))) if G(sqrt(G(x^2*exp(-x)))) = x */ {a(n) = my(G=x); for(i=1,n, G = serreverse( sqrt( subst(G,x, x^2*exp(-x +O(x^n))) ) )); A = subst(G,x,sqrt(subst(G,x,x^2*exp(x +O(x^n))))); n!*polcoeff(A,n)} for(n=1,30,print1(a(n),", ")) \\ Paul D. Hanna, Jun 06 2016 -
SageMath
def A100526(n): return 2^(1-n)*sum( k^(n-1)*binomial(n, k) for k in range(1,n+1) ) [A100526(n) for n in range(1,40)] # G. C. Greubel, Mar 27 2023
Formula
a(n) = (1/2^(n-1))*Sum_{k=1..n} k^(n-1)*binomial(n, k).
a(n) = n*A007889(n-1).
E.g.f.: -2*LambertW(-x*exp(x/2)/2). - Paul D. Hanna, Jun 07 2016, after Vladeta Jovovic's formula in A038049
E.g.f.: G( sqrt( G(x^2*exp(x)) ) ), where G( sqrt( G(x^2*exp(-x)) ) ) = x, and G(x) is the e.g.f. of A273952. - Paul D. Hanna, Jun 06 2016
a(n) ~ sqrt(1 + LambertW(exp(-1)))*n^(n-1) / (2^(n-1) * exp(n) * LambertW(exp(-1))^n). - Vaclav Kotesovec, Jun 23 2016