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

1, 1, 2, 4, 11, 32, 99, 318, 1051, 3550, 12200, 42520, 149930, 533890, 1917181, 6934722, 25243539, 92405718, 339940116, 1256122632, 4660081434, 17350844808, 64814186646, 242838410652, 912333763806, 3436240272972, 12972454874704, 49078874293528, 186051766180496

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn

Comments

Column 0 of A135333. - Emeric Deutsch, Dec 13 2007

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

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

From Petros Hadjicostas, Jul 27 2020: (Start)

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.

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

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.

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)

Examples

			a(4) = 11 because among the 14 (= A000108(4)) Dyck paths of semilength 4 the following paths do not qualify: UDUDUUDD, UUDDUDUD and UDUDUDUD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
• Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A000108, A000958, A135333.

Programs

Maple

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
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
# third Maple program:
a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],
     ((5*n-1)*a(n-1)+(11*n-28)*a(n-2)+(4*n-14)*a(n-3))/(2*n+2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 28 2015
A135339List := proc(m) local A, P, n; A := [1,1,2]; P := [1,2];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-2]]);
A := [op(A), P[-1]] od; A end: A135339List(28); # Peter Luschny, Mar 26 2022

Mathematica

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 *)

Formula

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

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

a(n) = A000958(n-1) + A000958(n). - Philippe Deléham, Dec 02 2009

a(n) ~ 25 * 4^(n - 1)/(9 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

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

Extensions

Edited and extended by Emeric Deutsch, Dec 13 2007