login
Number of Dyck paths containing exactly one UUUD.
2

%I #15 Jun 22 2014 17:04:18

%S 0,0,0,1,5,21,78,274,927,3061,9933,31824,100972,317942,995088,3099105,

%T 9612735,29715525,91595391,281643480,864189486,2646805668,8093543439,

%U 24713953515,75370741506,229604257846,698754428388,2124616182139

%N Number of Dyck paths containing exactly one UUUD.

%C a(n) = number of Dyck n-paths containing exactly one UUUD.

%C Conjecture: this is the Motzkin transform of the sequence of three zeros followed by A001651. - _R. J. Mathar_, Dec 11 2008

%H Vincenzo Librandi, <a href="/A108863/b108863.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f. (x-1+(1-2*x)M)/(x(1-3*x)(1+x*M)) = Sum_{n>=0}a(n)x^n where M = (1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2) is the gf for Motzkin numbers (A001006); satisfies z^3 = (1 + z)(1 - 3z)( (1 - 3z + z^2)G + z^2(1 - 3z)G^2 ).

%F Recurrence: (n-3)*(n+2)*a(n) = (n+1)*(5*n-14)*a(n-1) - 3*(n-2)*(n-1)*a(n-2) - 9*(n-2)*(n-1)*a(n-3). - _Vaclav Kotesovec_, Mar 22 2014

%F a(n) ~ 3^n/2 * (1-5*sqrt(3)/(2*sqrt(Pi*n))). - _Vaclav Kotesovec_, Mar 22 2014

%e a(4) = 5 because UUUUDDDD, UUUDUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD

%e each contain one UUUD.

%t CoefficientList[Series[(x-1+(1-2*x)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))/(x*(1-3*x)*(1+x*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))),{x,0,20}],x] (* _Vaclav Kotesovec_, Mar 22 2014 *)

%Y Cf. same as A055219 except for offset and is column k=1 of A091958. Dyck paths containing no UUUD are counted by the Motzkin numbers (A001006).

%Y Column k=8 of A243827.

%K nonn

%O 0,5

%A _David Callan_, Jul 25 2005