A114507 Number of Dyck paths of semilength n having no ascents of length 3.

1, 1, 2, 4, 10, 27, 79, 240, 750, 2387, 7711, 25214, 83315, 277799, 933596, 3159187, 10755190, 36811479, 126594819, 437220744, 1515844359, 5273760446, 18406122609, 64426136558, 226108087891, 795486834627, 2804993559426

Offset

0,3

Comments

Also number of ordered trees with n edges that have no vertices of outdegree 3.

Links

Table of n, a(n) for n=0..26.

Formula

G.f. G satisfies z^4*G^4-z^3*G^3+zG^2-G+1=0.

a(n) = 1/n*sum(j=ceiling((n+1)/2)..n, C(n,j)*C(4*j-2*n-2,j-1)*(-1)^(n-j)) n>0. [From Vladimir Kruchinin, Mar 07 2011]

D-finite with recurrence 2*n*(26405927*n-73197215)*(2*n+3)*(n+1)*a(n) +2*n*(2*n+1)*(26405927*n^2-273126414*n+480676927)*a(n-1) +4*(-793701648*n^4+4928830819*n^3-11073984912*n^2+10499531162*n-3092762541)*a(n-2) +2*(375778330*n^4-3447814000*n^3+22123257551*n^2-60324066977*n+51211836006)*a(n-3) +2*(12664700570*n^4-145150764350*n^3+621947195977*n^2-1179232268341*n+833841845214)*a(n-4) -3*(n-4)*(11017381441*n^3-111829680906*n^2+390445674963*n-461862831838)*a(n-5) -(n-4)*(n-5)*(30888861033*n^2-148676625095*n+156786419682)*a(n-6) +3206*(n-5)*(n-6)*(18970222*n-55906401)*(n-4)*a(n-7)=0. - R. J. Mathar, Jul 26 2022

Example

a(3) = 4 because we have UDUDUD, UDUUDD, UUDDUD and UUDUDD, where U=(1,1), D=(1,-1).

Maple

Order:=36: Y:=solve(series((Y-Y^2)/(1-Y^3+Y^4), Y)=z, Y): seq(coeff(Y, z^n), n=1..32); #(Y=zG)

Prog

(Maxima) a114507(n):= 1/n*sum(binomial(n, j)*binomial(4*j-2*n-2, j-1) *(-1)^(n-j), j, ceiling((n+1)/2), n); [Vladimir Kruchinin, Mar 07 2011].

Crossrefs

Cf. A102403, A114506, A114509.

Sequence in context: A108523 A157003 A245900 * A148105 A127386 A279551

Adjacent sequences: A114504 A114505 A114506 * A114508 A114509 A114510

Keyword

nonn

Author

Emeric Deutsch, Dec 03 2005

Status

approved