A371408 Number of Dyck paths of semilength n having exactly three (possibly overlapping) occurrences of the consecutive step pattern UDU, where U = (1,1) and D = (1,-1).

0, 0, 0, 0, 1, 4, 20, 80, 315, 1176, 4284, 15240, 53295, 183700, 625768, 2110472, 7057505, 23427600, 77271120, 253426752, 827009523, 2686728060, 8693388060, 28026897360, 90058925649, 288516259416, 921755412900, 2937377079000, 9338728806225, 29626186593276

Offset

0,6

Links

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

Wikipedia, Counting lattice paths

Formula

a(n) mod 2 = A121262(n) for n >= 1.

Example

a(4) = 1: UDUDUDUD.
a(5) = 4: UDUDUDUUDD, UDUDUUDUDD, UDUUDUDUDD, UUDUDUDUDD.

Maple

a:= n-> `if`(n<4, 0, binomial(n-1, 3)*add(binomial(n-3, j)*
         binomial(n-3-j, j-1), j=0..ceil((n-3)/2))/(n-3)):
seq(a(n), n=0..29);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [0$4, 1][n+1],
     (n-1)*((2*n-7)*a(n-1)+3*(n-2)*a(n-2))/((n-2)*(n-4)))
    end:
seq(a(n), n=0..29);

Crossrefs

Column k=3 of A091869.

Cf. A000108, A001006, A005717, A102839, A121262.

Sequence in context: A082138 A074358 A255050 * A292540 A320934 A344063

Adjacent sequences: A371405 A371406 A371407 * A371409 A371410 A371411

Keyword

nonn

Author

Alois P. Heinz, Mar 22 2024

Status

approved