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

Author

Emeric Deutsch, Nov 24 2004

Keywords

• nonn

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.

Crossrefs

Cf. A007889, A273952.

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