login
A212383
Number of Dyck n-paths all of whose ascents have lengths equal to 1 (mod 3).
6
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,5
COMMENTS
Lengths of descents are unrestricted.
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
EXAMPLE
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.
MAPLE
b:= proc(x, y, u) option remember;
`if`(x<0 or y<x, 0, `if`(x=0 and y=0, 1, b(x, y-1, true)+
`if`(u, add(b(x-(3*t+1), y, false), t=0..(x-1)/3), 0)))
end:
a:= n-> 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 *)
PROG
(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
CROSSREFS
Column k=3 of A212382.
Sequence in context: A362352 A099099 A074082 * A333881 A351968 A097813
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 12 2012
STATUS
approved