A333156 Number of Dyck paths with no UUU's and no DDD's, of semilength 2n and having exactly n (possibly overlapping) occurrences of the consecutive pattern UDUD, where U=(1,1) and D=(1,-1).

1, 1, 1, 8, 20, 84, 448, 1500, 8085, 37895, 161161, 874328, 4053140, 19724964, 103818660, 499182288, 2574393657, 13320605595, 66783194335, 351243492600, 1816922207100, 9395207816280, 49712099948160, 259448325851520, 1367225671234800, 7260061875376752

Offset: 0

Author

Alois P. Heinz, Mar 12 2020

Keywords

• nonn

Links

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

Crossrefs

Cf. A166288, A304361.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x or t=8, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 7, 4, 7, 2, 2, 8][t])
      +`if`(t=4, z, 1)  *b(x-1, y-1, [5, 3, 6, 3, 6, 8, 3][t]))))
    end:
a:= n-> coeff(b(4*n, 0, 1),z,n):
seq(a(n), n=0..30);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x || t == 8, 0,
    If[x == 0, 1, Expand[b[x-1, y+1, {2, 7, 4, 7, 2, 2, 8}[[t]]] +
    If[t == 4, z, 1]    *b[x-1, y-1, {5, 3, 6, 3, 6, 8, 3}[[t]]]]]];
a[n_] := Coefficient[b[4n, 0, 1], z, n];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz *)

Formula

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

From Vaclav Kotesovec, Mar 25 2020: (Start)

Recurrence: 43*(n-3)*(n-2)*(n-1)*n*(n+3)*(29329371*n^8 - 668927160*n^7 + 6506375706*n^6 - 35220417132*n^5 + 115953126831*n^4 - 237666494332*n^3 + 296611537564*n^2 - 207261219680*n + 63003153728)*a(n) = - 4*(n-3)*(n-2)*(n-1)*(87988113*n^10 - 1918793367*n^9 + 21033212895*n^8 - 166219084485*n^7 + 1012118366637*n^6 - 4429730336313*n^5 + 12942580570661*n^4 - 23748947161707*n^3 + 25109635302718*n^2 - 12660105337632*n + 1551575603232)*a(n-1) + (n-3)*(n-2)*(17333658261*n^11 - 430003268082*n^10 + 4720195682289*n^9 - 30488738625378*n^8 + 130209568442559*n^7 - 391419388419558*n^6 + 854545434284843*n^5 - 1354517078622998*n^4 + 1497954483509776*n^3 - 1053300009224368*n^2 + 388719936912768*n - 43770999939840)*a(n-2) + 2*(n-3)*(75523130325*n^12 - 2175626218950*n^11 + 27885098744163*n^10 - 209720413989444*n^9 + 1027277775429867*n^8 - 3437608878152710*n^7 + 8015815014349173*n^6 - 13049567806279672*n^5 + 14668786642708680*n^4 - 11184194641379704*n^3 + 5732514658835232*n^2 - 2001452813291520*n + 419517078888960)*a(n-3) - 9*(n-4)*(3*n - 13)*(3*n - 11)^2*(3*n - 10)*(29329371*n^8 - 434292192*n^7 + 2645107974*n^6 - 8587188480*n^5 + 16087282131*n^4 - 17700650032*n^3 + 11496031852*n^2 - 4736806800*n + 1286464896)*a(n-4).

a(n) ~ c * d^n / n^2, where d = 5.710108688327460098727830084... is the largest real root of equation 729 - 5150*d - 591*d^2 + 12*d^3 + 43*d^4 = 0 and c = 0.6168196189025568013359529457528774707879625027815570205940188285182461138... (End)