cp's OEIS Frontend

A135337 Number of Dyck paths of semilength n with no DUUU's starting at level 1.

%I A135337 #40 Mar 27 2022 22:29:49
%S A135337 1,1,2,5,13,36,105,320,1011,3289,10957,37216,128435,449142,1588228,
%T A135337 5669505,20403322,73945553,269647630,988642372,3642310793,13476857235,
%U A135337 50059454347,186598634398,697777187275,2616919372356,9840647362248
%N A135337 Number of Dyck paths of semilength n with no DUUU's starting at level 1.
%C A135337 Column 0 of A135331. - _Emeric Deutsch_, Dec 14 2007
%H A135337 G. C. Greubel, <a href="/A135337/b135337.txt">Table of n, a(n) for n = 0..1000</a>
%H A135337 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%F A135337 G.f.: 1+z*C^2/(1+z^3*C^4) = (1-z)*(2*C-1)/[(1-2*z)*C + z], where C = (1-sqrt(1-4*z))/(2*z) is the g.f. of the Catalan numbers (A000108). - _Emeric Deutsch_, Dec 14 2007
%F A135337 From _Gary W. Adamson_, Jul 26 2011: (Start)
%F A135337 a(n) = sum of top row terms of M^(n-1), M = an infinite square production matrix as follows, in which a column of [1,1,0,0,0,...] is prepended to an infinite lower triangular matrix of all 1's and the rest zeros:
%F A135337   1, 1, 0, 0, 0, 0, ...
%F A135337   1, 1, 1, 0, 0, 0, ...
%F A135337   0, 1, 1, 1, 0, 0, ...
%F A135337   0, 1, 1, 1, 1, 0, ...
%F A135337   0, 1, 1, 1, 1, 1, ...
%F A135337   ... (End)
%F A135337 a(n) ~ 3*4^(n+1)/(25*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014
%F A135337 a(n) = A059019(n+1) - A059019(n), n>0. - _Philippe Deléham_, Oct 02 2014
%F A135337 a(n) = Sum_{m=0..n} 1/(m+1)*Sum_{k=0..n-m} k*C(2*m-k+1,m-k+1)*C(n-m-1,n-m-k). - _Vladimir Kruchinin_, Jan 16 2018
%e A135337 a(4)=13 because among the 14 (=A000108(4)) Dyck paths of semilength 14 only UDUUUDDD does not qualify.
%e A135337 a(4) = 13 since the top row of M^3 = [4, 5, 3, 1, 0, 0, 0, ...] with 13 = (4 + 5 + 3 + 1).
%p A135337 a := -2*x+1-sqrt(1-4*x); b := 2*(sqrt(1-4*x)*x+x^2);
%p A135337 series((2*a+b)/(a+b), x=0, 30): seq(coeff(%,x,n), n=0..26); # after V. Kotesovec, _Peter Luschny_, Mar 20 2014
%t A135337 CoefficientList[Series[1+x*((1-Sqrt[1-4*x])/(2*x))^2/(1+x^3*((1-Sqrt[1-4*x])/(2*x))^4), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 20 2014 *)
%o A135337 (PARI) x='x+O('x^25); Vec(1+x*((1-sqrt(1-4*x))/(2*x))^2/(1+x^3*((1-sqrt(1-4*x))/(2*x))^4)) \\ _G. C. Greubel_, Feb 11 2017
%o A135337 (Maxima)
%o A135337 a(n):=sum(sum(k*binomial(2*m-k+1,m-k+1)*binomial(n-m-1,n-m-k),k,0,n-m)/(m+1),m,0,n); /* _Vladimir Kruchinin_, Jan 16 2018 */
%Y A135337 Cf. A000108, A135331.
%K A135337 nonn
%O A135337 0,3
%A A135337 _N. J. A. Sloane_, Dec 07 2007
%E A135337 More terms from _Emeric Deutsch_, Dec 14 2007