cp's OEIS Frontend

A135339 Number of Dyck paths of semilength n having no DUDU's starting at level 1.

%I A135339 #62 Sep 08 2024 22:39:14
%S A135339 1,1,2,4,11,32,99,318,1051,3550,12200,42520,149930,533890,1917181,
%T A135339 6934722,25243539,92405718,339940116,1256122632,4660081434,
%U A135339 17350844808,64814186646,242838410652,912333763806,3436240272972,12972454874704,49078874293528,186051766180496
%N A135339 Number of Dyck paths of semilength n having no DUDU's starting at level 1.
%C A135339 Column 0 of A135333. - _Emeric Deutsch_, Dec 13 2007
%C A135339 Apparently, for n > 0, a(n) is the number of Motzkin paths of length n-1 with two colors of flat step (F and f) and avoiding FF at level 0. E.g., for n = 3, the a(3) = 4 paths are UD, ff, fF and Ff. - _David Scambler_, Jun 27 2013
%C A135339 Number of standard Young tableaux of shape n^2 that avoid the consecutive pattern [12][34][56], read by columns. - _Ran Pan_, Sep 27 2015
%C A135339 From _Petros Hadjicostas_, Jul 27 2020: (Start)
%C A135339 Since an explicit formula for a(n) in terms of binomial coefficients is known (see _Emeric Deutsch_'s formula), the Wilf-Zeilberger method provides an easy proof of _R. J. Mathar_'s recurrence.
%C A135339 Let us suppose we know only the g.f. A(z) given in the Formula section below. Write the LHS(n) of _R. J. Mathar_'s recurrence as 2*(n + 1)*a(n) + (-5*(n-1) - 4)*a(n-1) + (-11*(n-2) + 6)*a(n-2) + 2*(-2*(n-3) + 1)*a(n-3), multiply by x^n, and sum from n = 3 to infinity. After some simple algebra, we get Sum_{n >= 3} LHS(n)*z^n = z*A'(z)*(2 - 5*z - 11*z^2 - 4*z^3) + A(z)*(2 - 4*z + 6*z^2 + 2*z^3) - (2 + 9*z^2).
%C A135339 We rationalize the denominator of A(z) and get A(z) = (2*z*C(z) - z + C(z))*(3 + sqrt(1 - 4*z))/(2*(z + 2)), where C(z) is the o.g.f. of A000108. Now substitute the formula for A(z) in the expression above and use a CAS (e.g., SageMath) to simplify.
%C A135339 We get that Sum_{n >= 3} LHS(n)*z^n = z^3. This means _R. J. Mathar_'s recurrence is correct for n >= 4, but gives 1 for n = 3. (End)
%H A135339 Alois P. Heinz, <a href="/A135339/b135339.txt">Table of n, a(n) for n = 0..1000</a>
%H A135339 Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]
%H A135339 Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.
%H A135339 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 A135339 G.f.: (2*z*C - z + C)/(1 + z*C), where C = (1 - sqrt(1 - 4*z))/(2*z) is the g.f. of the Catalan numbers (A000108). - _Emeric Deutsch_, Dec 13 2007
%F A135339 a(n) = binomial(2*n-2, n-1)/n + (Sum_{j=0..n-2} (-1)^j * (j + 3) * binomial(2*n-j-2, n))/(n+1) for n >= 1. - _Emeric Deutsch_, Dec 13 2007
%F A135339 a(n) = A000958(n-1) + A000958(n). - _Philippe Deléham_, Dec 02 2009
%F A135339 a(n) ~ 25 * 4^(n - 1)/(9 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014
%F A135339 Conjecture: 2*(n + 1)*a(n) + (-5*n + 1)*a(n-1) + (-11*n + 28)*a(n-2) + 2*(-2*n + 7)*a(n-3) = 0 for n >= 4. - _R. J. Mathar_, Oct 20 2015
%e A135339 a(4) = 11 because among the 14 (= A000108(4)) Dyck paths of semilength 4 the following paths do not qualify: UDUDUUDD, UUDDUDUD and UDUDUDUD.
%p A135339 G:=(2*z*C-z+C)/(1+z*C): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=series(G,z=0,30): seq(coeff(Gser,z,n),n=0..25); # _Emeric Deutsch_, Dec 13 2007
%p A135339 a:= proc (n) options operator, arrow: binomial(2*n-2, n-1)/n+(sum((-1)^j*(j+3)*binomial(2*n-j-2,n),j=0..n-2))/(n+1) end proc: 1, seq(a(n),n=1..25); # _Emeric Deutsch_, Dec 13 2007
%p A135339 # third Maple program:
%p A135339 a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],
%p A135339      ((5*n-1)*a(n-1)+(11*n-28)*a(n-2)+(4*n-14)*a(n-3))/(2*n+2))
%p A135339     end:
%p A135339 seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 28 2015
%p A135339 A135339List := proc(m) local A, P, n; A := [1,1,2]; P := [1,2];
%p A135339 for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-2]]);
%p A135339 A := [op(A), P[-1]] od; A end: A135339List(28); # _Peter Luschny_, Mar 26 2022
%t A135339 CoefficientList[Series[(2*x*(1-Sqrt[1-4*x])/(2*x)-x+(1-Sqrt[1-4*x])/(2*x))/(1+x*(1-Sqrt[1-4*x])/(2*x)), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 20 2014 *)
%Y A135339 Cf. A000108, A000958, A135333.
%K A135339 nonn
%O A135339 0,3
%A A135339 _N. J. A. Sloane_, Dec 07 2007
%E A135339 Edited and extended by _Emeric Deutsch_, Dec 13 2007