A243870 Number of Dyck paths of semilength n avoiding the consecutive steps UDUUUDDDUD (with U=(1,1), D=(1,-1)).

1, 1, 2, 5, 14, 41, 129, 419, 1395, 4737, 16338, 57086, 201642, 718855, 2583149, 9346594, 34023934, 124519805, 457889432, 1690971387, 6268769864, 23320702586, 87031840257, 325741788736, 1222429311437, 4598725914380, 17339388194985, 65514945338284

Offset

0,3

Comments

UDUUUDDDUD is the only Dyck path of semilength 5 that contains all eight consecutive step patterns of length 3.

Links

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

Formula

Recursion: see Maple program.

Maple

a:= proc(n) option remember; `if`(n<14, [1, 1, 2, 5, 14, 41,
       129, 419, 1395, 4737, 16338, 57086, 201642, 718855][n+1],
       ((4*n-2)*a(n-1) -(3*n-9)*a(n-4) +(10*n-41)*a(n-5)
       -(3*n-21)*a(n-8) +(8*n-64)*a(n-9) -(n-14)*a(n-10)
       -(n-11)*a(n-12) +(2*n-25)*a(n-13) +(14-n)*a(n-14))/(n+1))
    end:
seq(a(n), n=0..40);

Mathematica

a[n_] := a[n] = If[n<14, {1, 1, 2, 5, 14, 41, 129, 419, 1395, 4737, 16338, 57086, 201642, 718855}[[n+1]], ((4n-2)a[n-1] - (3n-9)a[n-4] + (10n-41)a[n-5] - (3n-21)a[n-8] + (8n-64)a[n-9] - (n-14)a[n-10] - (n-11)a[n-12] + (2n-25)a[n-13] + (14-n)a[n-14])/(n+1)];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 27 2021, after Alois P. Heinz *)

Crossrefs

Column k=0 of A243881.

Column k=738 of A243753.

Sequence in context: A036766 A366024 A222589 * A287968 A148322 A148323

Adjacent sequences: A243867 A243868 A243869 * A243871 A243872 A243873

Keyword

nonn

Author

Alois P. Heinz, Jun 13 2014

Status

approved