login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
1, 2, 6, 28, 180, 1476, 14728, 173216, 2346480, 35981200, 616111056, 11652662880, 241259095168, 5427319729664, 131818482923520, 3437894427590656, 95825936705566464, 2842834581982211328, 89435890422890433280, 2974081497762693670400, 104234511362034627442176 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
LINKS
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.
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
EXAMPLE
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
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 *)
PROG
(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
(Magma) [2^(1-n)*(&+[ k^(n-1)*Binomial(n, k): k in [1..n]]): n in [1..40]]; // G. C. Greubel, Mar 27 2023
(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
CROSSREFS
Sequence in context: A002435 A276911 A104018 * A200560 A303344 A355205
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Nov 24 2004
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)