login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A114997 Number of ordered trees with n edges and no unary or binary nodes. 3
0, 0, 1, 1, 1, 4, 8, 13, 31, 71, 144, 318, 729, 1611, 3604, 8249, 18803, 42907, 98858, 228474, 528735, 1228800, 2865180, 6693712, 15676941, 36807239, 86584783, 204060509, 481823778, 1139565120, 2699329341, 6403500057, 15211830451, 36183117255, 86171536894, 205459894230, 490417795075 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Also counts sequences of n natural numbers, excluding 1 and 2, such that the sum of every prefix is no more than its length.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

Nachum Dershowitz and Shmuel Zaks, More patterns in trees: Up and down, young and old, odd and even, SIAM J. Discrete Mathematics, 23 (2009), 447-465.

FORMULA

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

If A(x) is the g.f. for the sequence with a(0)=1, then x^3*A^3+x*A^2-(1 + x)*A+1 = 0. - Emeric Deutsch, Jan 13 2015

Let A(x) be the g.f. for the sequence with a(0)=1, then x*A(x) is the reversion of x/(1+x^2*sum(k>=1,x^k)). - Joerg Arndt, Aug 19 2012 (proved by Emeric Deutsch, Jan 13 2015)

Recurrence: (n+1)*(n+2)*(28*n^2 - 38*n - 15)*a(n) = -4*(n+1)*(14*n^3 - 12*n^2 + 7*n - 15)*a(n-1) + (n-2)*(140*n^3 + 90*n^2 - 221*n + 45)*a(n-2) + 6*(n-2)*(28*n^3 - 24*n^2 - 75*n + 95)*a(n-3) + 23*(n-3)*(n-2)*(28*n^2 + 18*n - 25)*a(n-4). - Vaclav Kotesovec, Mar 22 2014

a(n) ~ c / (n^(3/2) * r^n), where r = (4*sqrt(2) - 3 + 23*sqrt((344*sqrt(2))/529 - 235/529))/46 = 0.402505948621022106992... is the root of the equation 23*r^4+6*r^3+5*r^2-2*r-1 = 0 and c = sqrt((280 + 133*sqrt(2) - 25*sqrt(14*(11 + 8*sqrt(2)))) / (7*Pi))/4 = 0.273007516... - Vaclav Kotesovec, Mar 22 2014, updated Jan 14 2015

MAPLE

eq := x^3*A^3+x*A^2-(1+x)*A+1 = 0: A := RootOf(eq, A): Aser := series(A, x = 0, 40): seq(coeff(Aser, x, n), n = 1 .. 38); # Emeric Deutsch, Jan 13 2015

MATHEMATICA

Table[Sum[1/(n+1)*Binomial[n+1, k]*Binomial[2*k-n-3, n-k], {k, Ceiling[(n+3)/2], n}], {n, 1, 20}] (* Vaclav Kotesovec, Mar 22 2014 *)

PROG

(PARI) a(n)=sum(k=ceil((n+3)/2), n, (1/(n+1) * binomial(n+1, k) * binomial(2*k-n-3, n-k)) ); \\ Joerg Arndt, Aug 19 2012

(PARI) N=66; gf=serreverse(x/(1+x^2*sum(k=1, N, x^k))+O(x^N)) / x;

/* = 1 + x^3 + x^4 + x^5 + 4*x^6 + 8*x^7 + 13*x^8 + 31*x^9 + ... */

v114997=Vec(gf) /* = [1, 0, 0, 1, 1, 1, 4, 8, 13, 31, ...] */  \\ Joerg Arndt, Aug 19 2012

CROSSREFS

Cf. A000108 (rev. of x/(1+1*sum(k>=1,x^k)) ), A005043 (rev. of x/(1+x*sum(k>=1,x^k)), A215341 (rev. of x/(1+x^3*sum(k>=1,x^k)) ).

Sequence in context: A080003 A033016 A027008 * A146919 A312221 A312222

Adjacent sequences:  A114994 A114995 A114996 * A114998 A114999 A115000

KEYWORD

nonn

AUTHOR

Nachum Dershowitz, Feb 23 2006

EXTENSIONS

Offset set to 1 by Joerg Arndt, Aug 19 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:52 EDT 2020. Contains 334671 sequences. (Running on oeis4.)