A304361 Number of Dyck paths of semilength 2n having exactly n (possibly overlapping) occurrences of the consecutive pattern UDUD, where U=(1,1) and D=(1,-1).

1, 1, 1, 9, 41, 244, 1555, 10037, 68599, 476981, 3399518, 24652718, 181411439, 1352123760, 10185964435, 77458698781, 593871350009, 4586247704944, 35646681303447, 278665636846853, 2189789189667782, 17288684906561300, 137081212514315262, 1091163063187762414

Offset

0,4

Links

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

Vaclav Kotesovec, Recurrence (of order 6)

Wikipedia, Counting lattice paths

Formula

a(n) = A094507(2n,n).

a(n) ~ c * d^n / n^2, where d = 8.678461743575504549836851346229164298625429506253061911480810294... is the real root of equation 28*d^5 - 72*d^4 - 1119*d^3 - 3136*d^2 - 272*d - 16 = 0 and c = 0.15899091419445210968174633623072264522489566046427010886172717963... - Vaclav Kotesovec, Mar 25 2020

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])
        +b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
    end:
a:= n-> coeff(b(4*n, 0, 1), z, n):
seq(a(n), n=0..35);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0, If[x == 0, 1, Expand[ b[x - 1, y + 1, {2, 2, 4, 2}[[t]]] + b[x - 1, y - 1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]];
a[n_] := Coefficient[b[4*n, 0, 1], z, n];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

Crossrefs

Cf. A094507, A333156.

Sequence in context: A147283 A171422 A129793 * A146878 A177259 A247884

Adjacent sequences: A304358 A304359 A304360 * A304362 A304363 A304364

Keyword

nonn

Author

Alois P. Heinz, May 11 2018

Status

approved