login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A212383 Number of Dyck n-paths all of whose ascents have lengths equal to 1 (mod 3). 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Lengths of descents are unrestricted.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Vaclav Kotesovec, Asymptotic of subsequences of A212382

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: A128232 A099099 A074082 * A097813 A167821 A093041

Adjacent sequences:  A212380 A212381 A212382 * A212384 A212385 A212386

KEYWORD

nonn

AUTHOR

Alois P. Heinz, May 12 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 08:36 EDT 2019. Contains 322306 sequences. (Running on oeis4.)