A114509 -id:A114509 - cp's OEIS frontend

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, 9911529800630, 35090946422404, 124462137097349

Offset: 0

Emeric Deutsch, Dec 03 2005

nonn

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

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

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A102403, A114506, A114509.

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)

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); /* Works for n > 0. Returns a(n-1). Vladimir Kruchinin, Mar 07 2011 */

a(n)={n++; sum(j=n\2+1, n, binomial(n, j)*binomial(4*j-2*n-2, j-1)*(-1)^(n-j))/n} \\ Andrew Howroyd, Jan 24 2025

G.f. G satisfies z^4*G^4-z^3*G^3+zG^2-G+1=0.
a(n-1) = 1/n*sum(j=ceiling((n+1)/2)..n, binomial(n,j)*binomial(4*j-2*n-2,j-1)*(-1)^(n-j)) n>0. - 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

a(27) onwards from Andrew Howroyd, Jan 24 2025

A114508 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having k ascents of length 4 (0<=k<=floor(n/4)). Also number of ordered trees with n edges which have k vertices of outdegree 4.

Original entry on oeis.org

1, 1, 2, 5, 13, 1, 37, 5, 111, 21, 345, 84, 1104, 322, 4, 3611, 1215, 36, 12016, 4555, 225, 40548, 17028, 1210, 138414, 63636, 5940, 22, 477076, 238004, 27534, 286, 1657956, 891268, 122850, 2366, 5802920, 3342375, 533625, 15925, 20436910, 12552580

Offset: 0

Emeric Deutsch, Dec 03 2005

Row n has 1+floor(n/4) terms. Row sums yield the Catalan numbers (A000108). Column 0 yields A114509. Sum(kT(n,k),k=0..floor(n/4))=binomial(2n-5,n-4) (A002054).

			T(5,1)=5 because we have UDUUUUDDDD, UUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD and UUUUDUDDDD, where U=(1,1), D=(1,-1).
Triangle starts:
1;
1;
2;
5;
13,1;
37,5;
111,21;
345,84;
1104,322,4;
3611,1215,36;

Cf. A102402, A114506, A000108, A002054, A114509.

Order:=20: Y:=solve(series((Y-Y^2)/(1-(1-t)*Y^4+(1-t)*Y^5),Y)=z,Y): 1; for n from 1 to 17 do seq(coeff(t*coeff(Y,z^(n+1)),t^j),j=1..1+floor(n/4)) od; # yields sequence in triangular form

G.f. G=G(t, z) satisfies (1-t)z^5*G^5-(1-t)z^4*G^4+zG^2-G+1=0.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Maxima

PARI

Formula

Extensions