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

1, 1, 3, 20, 140, 1134, 9702, 87516, 817245, 7852130, 77135630, 771742608, 7839348244, 80661853300, 839138980500, 8813312133840, 93339369441540, 995827949882370, 10694044148599350, 115515073043785800, 1254354063204682440, 13685749828961247180

Offset: 0

Author

Alois P. Heinz, Mar 22 2024

Keywords

• nonn

Examples

			a(1) = 1: UDUD.
a(2) = 3: UDUDUUDD, UDUUDUDD, UUDUDUDD.
a(3) = 20: UDUDUDUUDDUD, UDUDUDUUUDDD, UDUDUUDDUDUD, UDUDUUDUDDUD, UDUDUUDUUDDD, UDUDUUUDUDDD, UDUUDDUDUDUD, UDUUDUDDUDUD, UDUUDUDUDDUD, UDUUDUDUUDDD, UDUUDUUDUDDD, UDUUUDUDUDDD, UUDDUDUDUDUD, UUDUDDUDUDUD, UUDUDUDDUDUD, UUDUDUDUDDUD, UUDUDUDUUDDD, UUDUDUUDUDDD, UUDUUDUDUDDD, UUUDUDUDUDDD.
a(4) = 140: UDUDUDUDUUDDUUDD, UDUDUDUDUUUDDDUD, UDUDUDUDUUUDDUDD, ..., UUUDUDUUDUDUDDDD, UUUDUUDUDUDUDDDD, UUUUDUDUDUDUDDDD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..932
• Wikipedia, Counting lattice paths

Crossrefs

Cf. A000108, A081294, A091869.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 1, (2*(n-1)*(2*n-1)^2*
      a(n-1)+12*(n-2)*(2*n-1)*(2*n-3)*a(n-2))/((n+1)*n*(n-1)))
    end:
seq(a(n), n=0..21);

Formula

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

a(n) mod 2 = 1 <=> n in { round(2^(2*k-3)) : k >= 0 } = { A081294 } U { 0 }.