login
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).
3

%I #15 Mar 25 2024 16:35:13

%S 0,0,0,0,1,4,20,80,315,1176,4284,15240,53295,183700,625768,2110472,

%T 7057505,23427600,77271120,253426752,827009523,2686728060,8693388060,

%U 28026897360,90058925649,288516259416,921755412900,2937377079000,9338728806225,29626186593276

%N 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).

%H Alois P. Heinz, <a href="/A371408/b371408.txt">Table of n, a(n) for n = 0..2090</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

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

%e a(4) = 1: UDUDUDUD.

%e a(5) = 4: UDUDUDUUDD, UDUDUUDUDD, UDUUDUDUDD, UUDUDUDUDD.

%p a:= n-> `if`(n<4, 0, binomial(n-1, 3)*add(binomial(n-3, j)*

%p binomial(n-3-j, j-1), j=0..ceil((n-3)/2))/(n-3)):

%p seq(a(n), n=0..29);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<5, [0$4, 1][n+1],

%p (n-1)*((2*n-7)*a(n-1)+3*(n-2)*a(n-2))/((n-2)*(n-4)))

%p end:

%p seq(a(n), n=0..29);

%Y Column k=3 of A091869.

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

%K nonn

%O 0,6

%A _Alois P. Heinz_, Mar 22 2024