Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.1

Returns and Hills on Generalized Dyck Paths

Naiomi T. Cameron
Department of Mathematical Sciences
Lewis & Clark College
Portland, OR 97219

Jillian E. McLeod
Department of Mathematics
U.S. Coast Guard Academy
New London, CT 06320


In 2009, Shapiro posed the following question: "What is the asymptotic proportion of Dyck paths having an even number of hills?" In this paper, we answer Shapiro's question, as well as a generalization of the question to ternary paths. We find that the probability that a randomly chosen ternary path has an even number of hills approaches 125/169 as the length of the path approaches infinity. Our strategy relies on properties of the Fine number sequence and extends certain relationships between the Catalan and Fine number generating functions.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A000957 A001006 A001764 A006013 A008292 A023053 A033184 A036765 A051255 A065600 A065601 A101371 A109971 A110616.)

Received February 5 2016; revised versions received May 19 2016; June 13 2016. Published in Journal of Integer Sequences, June 15 2016.

Return to Journal of Integer Sequences home page