A138860 -id:A138860 - cp's OEIS frontend

A007889 Number of intransitive (or alternating, or Stanley) trees: vertices are [0,n] and for no i

1, 1, 2, 7, 36, 246, 2104, 21652, 260720, 3598120, 56010096, 971055240, 18558391936, 387665694976, 8787898861568, 214868401724416, 5636819806209792, 157935254554567296, 4707152127520549120, 148704074888134683520, 4963548160096887021056, 174553183413968718996736

Offset: 0

Alexander Postnikov [ apost(AT)math.mit.edu ]

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

Number of regions of the Linial arrangement. - Ira M. Gessel, Nov 01 2023

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, Birkhäuser, 1997.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.41(a).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
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, 2009-2010. [_N. J. A. Sloane_, Sep 27 2010]
G. Hetyei, Efron's coins and the Linial arrangement, arXiv preprint arXiv:1511.04482 [math.CO], 2015.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
A. Postnikov, Intransitive Trees, J. Combin. Theory Ser. A 79 (1997), 360-366.
Richard P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. USA 93 (1996), 2620-2625.
Index entries for sequences related to trees

Cf. A038049, A138860, A283828, A323841.

Row sums of A029847.

f:= n->1/(2^n*(n+1))*add(binomial(n+1, k)*k^n, k=1..(n+1)): seq(f(n), n=0..19);

With[{nn=20},CoefficientList[Series[-2/x LambertW[-1/2x Exp[x/2]], {x,0,nn}], x]Range[0,nn]!] (* Harvey P. Dale, Aug 12 2011 *)
Table[1/((n+1)2^n) Sum[Binomial[n+1,k]k^n,{k,n+1}],{n,0,20}] (* Harvey P. Dale, Apr 21 2012 *)

{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

/* 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

def A007889(n) : return add(binomial(n,k)*(k+1)^(n-1) for k in (0..n))/2^n
for n in (0..19) : print(A007889(n)) # Peter Luschny, Feb 29 2012

a(n) = (1/((n+1)*2^n))*Sum_{k=1..n+1} C(n+1,k)*k^n.
E.g.f. A(x) 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, Mar 29 2008
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). [Vladimir Shevelev, Mar 21 2010]
For n>0, a(n) = A088789(n+1)*2/(n+1). [Vaclav Kotesovec, Dec 26 2011]

A202617 E.g.f. satisfies: A(x) = exp( x*(1 + A(x)^2)/2 ).

Original entry on oeis.org

1, 1, 3, 19, 185, 2441, 40747, 823691, 19564785, 534145105, 16482667091, 567343245635, 21552042260905, 895664877901145, 40422799315249275, 1968883362773653051, 102942561775293158369, 5750760587905912310177, 341848844954020959953059, 21545207157567497255044979

Offset: 0

Paul D. Hanna, Dec 21 2011

nonn

Compare to e.g.f. F(x) of A007889: F(x) = exp(x*(1 + F(x))/2), where A007889(n) = number of intransitive (or alternating) trees: vertices are [0,n] and for no i

Related sequence: A058014(n) = number of labeled trees with n+1 nodes such that the degrees of all nodes, excluding the first node, are odd.

			E.g.f.: A(x) = 1 + x + 3*x^2/2! + 19*x^3/3! + 185*x^4/4! + 2441*x^5/5! +...
where log(A(x)) = x*(1 + A(x)^2)/2 and
log(A(x)) = x + 2*x^2/2! + 12*x^3/3! + 112*x^4/4! + 1440*x^5/5! + 23616*x^6/6! +...
A(x)^2 = 1 + 2*x + 8*x^2/2! + 56*x^3/3! + 576*x^4/4! + 7872*x^5/5! + 134656*x^6/6! +...

Seiichi Manyama, Table of n, a(n) for n = 0..372

Cf. A007889, A058014, A214225, A138860, A202357.

CoefficientList[Series[Sqrt[-ProductLog[-E^x*x]/x], {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Jan 10 2014 *)

a(n)=local(A=1+x); for(i=0, n, A=exp(x*(1+A^2)/2 +x*O(x^n))); n!*polcoeff(A, n)

/* Coefficients of A(x)^p are given by: */
{a(n, p=1)=(1/2^n)*sum(k=0, n, binomial(n, k)*p*(2*k+p)^(n-1))}

a(n)=n!*polcoeff(exp(sum(k=1,n,k^(k-1)*cosh(k*x +x*O(x^n))*x^k/k!) +x*O(x^n)),n)
for(n=0,25,print1(a(n),", ")) \\ Paul D. Hanna, Nov 20 2012

E.g.f. A(x) equals the formal inverse of function 2*log(x)/(1+x^2).
E.g.f.: exp( Sum_{n>=1} n^(n-1) * cosh(n*x) * x^n / n! ). - Paul D. Hanna, Nov 20 2012
E.g.f.: exp(G(x)) where G(x) = x/(1 - tanh(G(x))) is the e.g.f. of A214225. - Paul D. Hanna, Nov 20 2012
E.g.f. satisfies: A(x) = G(x*A(x)) where G(x) = A(x/G(x)) is the e.g.f. of A058014.
a(n) = (1/2^n)*Sum_{k=0..n} C(n,k)*(2*k+1)^(n-1).
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*(2*k+p)^(n-1).
a(n) ~ sqrt(1+c) * n^(n-1) / (2 * exp(n) * c^(n+1/2)), where c = LambertW(exp(-1)) = 0.278464542761... (see A202357). - Vaclav Kotesovec, Jan 10 2014
E.g.f.: sqrt(-LambertW(-x*exp(x))/x). - Vaclav Kotesovec, Jan 10 2014

A138764 E.g.f. A(x) equals the inverse function of log(x)/(x + x^2).

Original entry on oeis.org

1, 2, 16, 248, 5824, 184512, 7379200, 356956672, 20274442240, 1322971320320, 97542692798464, 8020249539919872, 727662513046159360, 72215332738579824640, 7782298855258810482688, 905031449967822916026368

Offset: 0

Paul D. Hanna, Mar 29 2008

nonn

Let r = radius of convergence of A(x), then:
r = 0.116689393840305520533609707610483991781804638898970699779...
A(r) = 1.835037067429188745641951736620284283425600418229813004773...
where A(r) and r satisfy:
A(r) = exp( (1 + A(r))/(1 + 2*A(r)) ) and r = 1/(A(r)*(1 + 2*A(r))).
Also, r = (1-t)^2/(t*(1+t)) where (t/(1-t))^(1+t) = e. [Paul D. Hanna, Oct 03 2020, derived from the asymptotic formula given by Vaclav Kotesovec].

			E.g.f. A(x) = 1 + 2x + 16x^2/2! + 248x^3/3! + 5824x^4/4! +...

Seiichi Manyama, Table of n, a(n) for n = 0..331

Cf. A138860.

Table[Sum[Binomial[n,k]*(n+k+1)^(n-1),{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Jun 15 2013 *)

{a(n) = local(A=1+x); for(i=0,n, A=exp(x*(A+A^2 +x*O(x^n) ))); n! * polcoeff(A,n) }

{a(n) = sum(k=0, n, binomial(n, k)*(n+k+1)^(n-1))}

E.g.f. satisfies: A(x) = exp( x*[A(x) + A(x)^2] ).
a(n) = Sum_{k=0..n} binomial(n,k)*(n+k+1)^(n-1) - Vladeta Jovovic, Mar 31 2008.
a(n) = A138860(n)*2^n.
E.g.f. satisfies: A( x/( exp(x) + exp(2*x) ) ) = exp(x).
a(n) ~ n^(n-1)*(1+r)^n*r^(n+1)/(sqrt(1+3*r)*(1-r)^(2*n+1)*exp(n)), where r = 0.6472709258412625... is the root of the equation (r/(1-r))^(1+r) = e. - Vaclav Kotesovec, Jun 15 2013

A138903 a(n) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*(n+k)^(n-1).

Original entry on oeis.org

1, 3, 21, 234, 3590, 70254, 1672972, 46955760, 1517994792, 55549351800, 2269918543640, 102452561694864, 5062050729973120, 271751784988056576, 15750949414628405760, 980315266648197537792, 65207656047198387921536

Offset: 1

Paul D. Hanna and Vladeta Jovovic, Apr 02 2008, Apr 03 2008

A138903 := proc(n) local k ; add(binomial(n,k)*(n+k)^(n-1),k=0..n)/2^n ; end: seq(A138903(n),n=1..20) ; # R. J. Mathar, Apr 12 2008

Table[1/2^n * Sum[Binomial[n,k]*(n+k)^(n-1),{k,0,n}],{n,1,20}] (* Vaclav Kotesovec, Jun 15 2013 *)

{a(n)=local(X=x+x*O(x^n)); n!*polcoeff(serreverse(2*x/(exp(X)+exp(2*X)) ), n)}

E.g.f.: A(x) = log(B(x)), where B(x) is e.g.f. of A138860.
E.g.f.: A(x) = Series_Reversion[ 2*x/(exp(x) + exp(2*x)) ].
a(n) ~ n^(n-1)*(1+r)^n*r^n/(sqrt(1+3*r)*(1-r)^(2*n)*exp(n)*2^n), where r = 0.6472709258412625... is the root of the equation (r/(1-r))^(1+r) = e. - Vaclav Kotesovec, Jun 15 2013

More terms from R. J. Mathar, Apr 12 2008

A372177 E.g.f. A(x) satisfies A(x) = exp( x * A(x)^(1/2) * (1 + A(x)^(1/2)) ).

Original entry on oeis.org

1, 2, 10, 86, 1072, 17652, 362692, 8950216, 258135136, 8525942000, 317455926544, 13159289478480, 601125054656320, 30006335335032448, 1625132762002203136, 94920040351049627648, 5947667725489120124416, 397991563599617527723776

Offset: 0

Seiichi Manyama, Apr 23 2024

nonn

Cf. A138860, A372232.

a(n, r=1, t=1/2, u=1/2) = r*sum(k=0, n, (t*n+u*k+r)^(n-1)*binomial(n, k));

E.g.f.: A(x) = B(x)^2 where B(x) is the e.g.f. of A138860.

If e.g.f. satisfies A(x) = exp( r*x*A(x)^(t/r) * (1 + A(x)^(u/r)) ), then a(n) = r * Sum_{k=0..n} (t*n+u*k+r)^(n-1) * binomial(n,k).

A372251 E.g.f. A(x) satisfies A(x) = exp( x * A(x)^2 * (1 + A(x))/2 ).

Original entry on oeis.org

1, 1, 6, 73, 1364, 34586, 1110496, 43207004, 1976199792, 103925934712, 6178846168976, 409847155094840, 30007066358487040, 2403751529017358144, 209131503815967330816, 19637892118783264231936, 1979605910448187576510208, 213226210180592877512104832

Offset: 0

Seiichi Manyama, Apr 24 2024

nonn

Cf. A138860, A372246.

a(n) = sum(k=0, n, (n+k/2+1/2)^(n-1)*binomial(n, k))/2;

a(n) = 1/2 * Sum_{k=0..n} (n+k/2+1/2)^(n-1) * binomial(n,k).

a(n) ~ sqrt((1 + s)/(4 + 9*s)) * s^(2*n + 1) * (2 + 3*s)^n * n^(n-1) / (2^n * exp(n)), where s = 1.470103625022272111740158699814771551850270522048... is the root of the equation log(s) = (1 + s)/(2 + 3*s). - Vaclav Kotesovec, Apr 24 2024

Showing 1-6 of 6 results.

cp's OEIS Frontend

A007889 Number of intransitive (or alternating, or Stanley) trees: vertices are [0,n] and for no i

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A202617 E.g.f. satisfies: A(x) = exp( x*(1 + A(x)^2)/2 ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A138764 E.g.f. A(x) equals the inverse function of log(x)/(x + x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A138903 a(n) = (1/2^n)* Sum_{k=0..n} binomial(n,k)*(n+k)^(n-1).

Views

Author

Keywords

Programs

Maple

Mathematica

PARI

Formula

Extensions

A372177 E.g.f. A(x) satisfies A(x) = exp( x * A(x)^(1/2) * (1 + A(x)^(1/2)) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A372251 E.g.f. A(x) satisfies A(x) = exp( x * A(x)^2 * (1 + A(x))/2 ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula