

A102407


Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.


4



1, 1, 2, 4, 10, 26, 72, 206, 606, 1820, 5558, 17206, 53872, 170298, 542778, 1742308, 5627698, 18277698, 59652952, 195541494, 643506310, 2125255036, 7041631854, 23400092142, 77971706848, 260458050034, 872040564850, 2925902656644, 9836517749658, 33130048199466
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of Łukasiewicz paths of length n having no level steps at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: a(2)=2 because we have HH and UD, where U=(1,1), H=(1,0) and D=(1,1). Column 0 of A102405.
a(n) is the number of Dyck npaths containing no DUDUs. For example, a(3) = 4 counts all five Dyck 3paths except UDUDUD.
a(n) is the number of Dyck npaths containing no subpath of the form UUPDD where P is a nonempty Dyck path. For example, a(3) = 4 counts all five Dyck 3paths except UUUDDD. Deutsch's involution phi on Dyck paths interchanges #DUDUs and #UUPDDs with P a nonempty Dyck path. Phi is defined recursively by phi({})={}, phi(UPDQ)=U phi(Q) D phi(P) where P,Q are Dyck paths.
a(n) is the number of ordered trees on n edges in which each leaf is either the leftmost or rightmost child of its parent. For example, a(3) counts:
.........../\.../\
./ \..............
.......
(End)


LINKS



FORMULA

G.f.: (1+zz^2sqrt(12z5z^22z^3+z^4))/(2z).
For an explicit formula (from Sapounakis et al.) see the Maple program.
Let M = the following infinite square production matrix (where the main diagonal is (1,0,1,0,1,0,...):
1, 1, 0, 0, 0, 0, ...
1, 0, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 0, ...
...
a(n) = top left term in M^n, a(n+1) = sum of top row terms in M^n. Example: top row of M^5 = (26, 19, 16, 7, 3, 1, 0, 0, 0, ...) where 26 = a(5) and 72 = a(6) = (26 + 19 + 16 + 7 + 3 + 1).  Gary W. Adamson, Jul 11 2011
Conjecture: (n+1)*a(n) +(2*n+1)*a(n1) +5*(n+2)*a(n2) +(2*n+7)*a(n3) +(n5)*a(n4)=0.  R. J. Mathar, Jan 04 2017


EXAMPLE

a(3)=4 because among the five Dyck paths of semilength 3 only UUDUDD has an ascent of length 1 that starts at an odd level; here U=(1,1) and D=(1,1).


MAPLE

G:=(1+zz^2sqrt(12*z5*z^22*z^3+z^4))/2/z: Gser:=series(G, z=0, 31): 1, seq(coeff(Gser, z^n), n=1..29);
f:=proc(n) local i, j; add( (1/(nj))*binomial(nj, j)* add( binomial(n2*j, i)*binomial(j+i, n2*ji+1), i=0..n2*j), j=0..n/2 ); end; # N. J. A. Sloane, Dec 06 2007


MATHEMATICA

CoefficientList[Series[(1 + x  x^2  Sqrt[1  2 x  5 x^2  2 x^3 + x^4]) / (2 x), {x, 0, 30}], x] (* Vincenzo Librandi, Mar 20 2015 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



