login
A114507
Number of Dyck paths of semilength n having no ascents of length 3.
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.
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 03 2005
STATUS
approved