A212383 Number of Dyck n-paths all of whose ascents have lengths equal to 1 (mod 3).

1, 1, 1, 1, 2, 6, 16, 37, 83, 199, 512, 1343, 3488, 9011, 23488, 62094, 165738, 444160, 1193146, 3216436, 8709766, 23683846, 64611879, 176730460, 484593740, 1332018207, 3669981318, 10133197561, 28032766982, 77688769031, 215665451243, 599644845226

Offset: 0

Author

Alois P. Heinz, May 12 2012

Keywords

• nonn

Comments

Lengths of descents are unrestricted.

Examples

			a(0) = 1: the empty path.
a(1) = 1: UD.
a(2) = 1: UDUD.
a(3) = 1: UDUDUD.
a(4) = 2: UDUDUDUD, UUUUDDDD.
a(5) = 6: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD, UUUUDUDDDD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Vaclav Kotesovec, Asymptotic of subsequences of A212382

Crossrefs

Column k=3 of A212382.

Programs

Maple

b:= proc(x, y, u) option remember;
      `if`(x<0 or y b(n$2, true):
seq(a(n), n=0..40);
# second Maple program
a:= n-> coeff(series(RootOf(A=1+x*A/(1-(x*A)^3), A), x, n+1), x, n):
seq(a(n), n=0..40);

Mathematica

For[A = 1; n = 1, n <= 32, n++, A = (1-(x*A)^3)/(1-x-(x*A)^3) + O[x]^n]; CoefficientList[A, x] (* Jean-François Alcover, Apr 23 2016 *)

Maxima

a(n):=sum(binomial(2*k-n-1,n-k)*binomial(n+1,3*k-2*n),k,0,n)/(n+1); /* Vladimir Kruchinin, Mar 05 2016 */

PARI

a(n) = sum(k=0, n, binomial(2*k-n-1,n-k)*binomial(n+1,3*k-2*n)) /(n+1); \\ Michel Marcus, Mar 05 2016

PARI

x='x+O('x^66);  Vec( serreverse( x/(1+x/(1-x^3)) ) / x ) \\ Joerg Arndt, Apr 23 2016

Formula

G.f. satisfies: A(x) = 1+x*A(x)/(1-(x*A(x))^3).

Recurrence: 27*(n-2)*n*(n+1)*(7315*n^5 - 103740*n^4 + 581321*n^3 - 1621860*n^2 + 2283420*n - 1319472)*a(n) = 18*n*(43890*n^7 - 732165*n^6 + 5094566*n^5 - 19117342*n^4 + 41486098*n^3 - 51106565*n^2 + 31574358*n - 6550776)*a(n-1) - 6*(197505*n^8 - 3591000*n^7 + 27966247*n^6 - 121632688*n^5 + 321488424*n^4 - 523324472*n^3 + 503478200*n^2 - 254789904*n + 49688640)*a(n-2) + 3*(395010*n^8 - 7774515*n^7 + 66666259*n^6 - 325204119*n^5 + 983833331*n^4 - 1877089982*n^3 + 2181330624*n^2 - 1388626960*n + 361350720)*a(n-3) + 3*(n-4)*(460845*n^7 - 7918155*n^6 + 56450863*n^5 - 217083355*n^4 + 489279096*n^3 - 653902178*n^2 + 488647076*n - 160632720)*a(n-4) - 3*(n-5)*(n-4)*(43890*n^6 - 600495*n^5 + 3490586*n^4 - 10880637*n^3 + 18337012*n^2 - 14599068*n + 3573072)*a(n-5) - 23*(n-6)*(n-5)*(n-4)*(7315*n^5 - 67165*n^4 + 239511*n^3 - 427187*n^2 + 405278*n - 173016)*a(n-6). - Vaclav Kotesovec, Aug 18 2013

a(n) ~ c*d^n/n^(3/2), where d = 2.917020449755... is the root of the equation 23 + 18*d - 189*d^2 - 162*d^3 + 162*d^4 - 108*d^5 + 27*d^6 = 0 and c = 0.415028509255451481644332... - Vaclav Kotesovec, Aug 18 2013

a(n) = Sum_{k=0..n} binomial(2*k-n-1,n-k)*binomial(n+1,3*k-2*n)/(n+1). - Vladimir Kruchinin, Mar 05 2016

G.f. is series_reversion(B(x))/x where B(x) = x/(1 + x + x^4 + x^7 + x^10 + ...) = x/(1+x/(1-x^3)); for Dyck paths with allowed ascent lengths {u_1, u_2, ...} use B(x) = x/( 1 + sum(k>=1, x^{u_k} ) ). - Joerg Arndt, Apr 23 2016