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

%I #47 Dec 22 2020 03:54:33

%S 1,1,1,8,20,84,448,1500,8085,37895,161161,874328,4053140,19724964,

%T 103818660,499182288,2574393657,13320605595,66783194335,351243492600,

%U 1816922207100,9395207816280,49712099948160,259448325851520,1367225671234800,7260061875376752

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

%H Alois P. Heinz, <a href="/A333156/b333156.txt">Table of n, a(n) for n = 0..1330</a>

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

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

%F From _Vaclav Kotesovec_, Mar 25 2020: (Start)

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

%F 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)

%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x or t=8, 0,

%p `if`(x=0, 1, expand(b(x-1, y+1, [2, 7, 4, 7, 2, 2, 8][t])

%p +`if`(t=4, z, 1) *b(x-1, y-1, [5, 3, 6, 3, 6, 8, 3][t]))))

%p end:

%p a:= n-> coeff(b(4*n, 0, 1),z,n):

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

%t b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x || t == 8, 0,

%t If[x == 0, 1, Expand[b[x-1, y+1, {2, 7, 4, 7, 2, 2, 8}[[t]]] +

%t If[t == 4, z, 1] *b[x-1, y-1, {5, 3, 6, 3, 6, 8, 3}[[t]]]]]];

%t a[n_] := Coefficient[b[4n, 0, 1], z, n];

%t a /@ Range[0, 30] (* _Jean-François Alcover_, Dec 22 2020, after _Alois P. Heinz_ *)

%Y Cf. A166288, A304361.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Mar 12 2020