A114997 Number of ordered trees with n edges and no unary or binary nodes.

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

Offset: 1

Author

Nachum Dershowitz, Feb 23 2006

Keywords

• nonn

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.

a(n) is the number of Dyck paths of semilength n with all ascents of length >= 3. For example, a(6) = 4 counts U^6.D^6, U^3.D.U^3.D^5, U^3.D^2.U^3.D^4, U^3.D^3.U^3.D^3 where ^ denotes repetition and a dot denotes concatenation. - David Callan, Dec 08 2021

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.

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) ).

Programs

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

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

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

Extensions

Offset set to 1 by Joerg Arndt, Aug 19 2012