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,3

Links

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

Wikipedia, Counting lattice paths

Formula

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

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

Example

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.

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);

Crossrefs

Cf. A000108, A081294, A091869.

Sequence in context: A163065 A082143 A342055 * A009156 A074573 A068571

Adjacent sequences: A371408 A371409 A371410 * A371412 A371413 A371414

Keyword

nonn

Author

Alois P. Heinz, Mar 22 2024

Status

approved