login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
From David Callan, Sep 25 2006: (Start)
a(n) is the number of Dyck n-paths containing no DUDUs. For example, a(3) = 4 counts all five Dyck 3-paths except UDUDUD.
a(n) is the number of Dyck n-paths containing no subpath of the form UUPDD where P is a nonempty Dyck path. For example, a(3) = 4 counts all five Dyck 3-paths 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
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
FORMULA
G.f.: (1+z-z^2-sqrt(1-2z-5z^2-2z^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(n-1) +5*(-n+2)*a(n-2) +(-2*n+7)*a(n-3) +(n-5)*a(n-4)=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+z-z^2-sqrt(1-2*z-5*z^2-2*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/(n-j))*binomial(n-j, j)* add( binomial(n-2*j, i)*binomial(j+i, n-2*j-i+1), i=0..n-2*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
Sequence in context: A180023 A154835 A049145 * A358455 A356832 A148097
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 06 2005
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 03:04 EST 2024. Contains 370219 sequences. (Running on oeis4.)