|
| |
|
|
A135339
|
|
Number of Dyck paths of semilength n having no DUDU's starting at level 1.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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
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
|
|
|
|
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
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:
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
