cp's OEIS Frontend

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.

%I A100526 #26 Mar 28 2023 08:00:35
%S A100526 1,2,6,28,180,1476,14728,173216,2346480,35981200,616111056,
%T A100526 11652662880,241259095168,5427319729664,131818482923520,
%U A100526 3437894427590656,95825936705566464,2842834581982211328,89435890422890433280,2974081497762693670400,104234511362034627442176
%N 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.
%H A100526 G. C. Greubel, <a href="/A100526/b100526.txt">Table of n, a(n) for n = 1..400</a>
%H A100526 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 A100526 A. Postnikov, <a href="https://doi.org/10.1006/jcta.1996.2735">Intransitive Trees</a>, J. Combin. Theory Ser. A 79 (1997), 360-366.
%F A100526 a(n) = (1/2^(n-1))*Sum_{k=1..n} k^(n-1)*binomial(n, k).
%F A100526 a(n) = n*A007889(n-1).
%F A100526 E.g.f.: -2*LambertW(-x*exp(x/2)/2). - _Paul D. Hanna_, Jun 07 2016, after Vladeta Jovovic's formula in A038049
%F A100526 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
%F A100526 a(n) ~ sqrt(1 + LambertW(exp(-1)))*n^(n-1) / (2^(n-1) * exp(n) * LambertW(exp(-1))^n). - _Vaclav Kotesovec_, Jun 23 2016
%e A100526 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 A100526 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! +...
%e A100526 Given G(x) such that G( sqrt( G(x^2*exp(-x)) ) ) = x, where
%e A100526 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)!) +...
%e A100526 then A(x) = G( sqrt( G(x^2*exp(x)) ) ). - _Paul D. Hanna_, Jun 06 2016
%p A100526 seq((1/2^(n-1))*add(k^(n-1)*binomial(n,k),k=1..n),n=1..22);
%t A100526 Rest[CoefficientList[Series[-2*LambertW[-x*E^(x/2)/2], {x, 0, 20}], x] * Range[0, 20]!] (* _Vaclav Kotesovec_, Jun 23 2016 *)
%o A100526 (PARI) /* Egf A(x) = G(sqrt(G(x^2*exp(x)))) if G(sqrt(G(x^2*exp(-x)))) = x */
%o A100526 {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)}
%o A100526 for(n=1,30,print1(a(n),", ")) \\ _Paul D. Hanna_, Jun 06 2016
%o A100526 (Magma) [2^(1-n)*(&+[ k^(n-1)*Binomial(n, k): k in [1..n]]): n in [1..40]]; // _G. C. Greubel_, Mar 27 2023
%o A100526 (SageMath)
%o A100526 def A100526(n): return 2^(1-n)*sum( k^(n-1)*binomial(n, k) for k in range(1,n+1) )
%o A100526 [A100526(n) for n in range(1,40)] # _G. C. Greubel_, Mar 27 2023
%Y A100526 Cf. A007889, A273952.
%K A100526 nonn
%O A100526 1,2
%A A100526 _Emeric Deutsch_, Nov 24 2004