OFFSET
0,3
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)
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.
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) ~ 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
EXAMPLE
a(4) = 11 because among the 14 (= A000108(4)) Dyck paths of semilength 4 the following paths do not qualify: UDUDUUDD, UUDDUDUD and UDUDUDUD.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 07 2007
EXTENSIONS
Edited and extended by Emeric Deutsch, Dec 13 2007
STATUS
approved