On the Number of Restricted Dyck Paths


Aleksandar Ilić, Andreja Ilić




We examine the number of integer lattice paths consisting of up-steps $(1,1)$ and down-steps $(1,-1)$ that do not touch the lines $y=m$ and $y=-k$, and in particular Theorem 3.2 in [P. Mladenovi\'c, {\it Combinatorics}, Mathematical Society of Serbia, Belgrade, 2001]. The theorem is shown to be incorrect for $n\geq m+k+\min(m,k)$, and using similar combinatorial technique we proved the upper and lower bound for the number of such restricted Dyck paths. In conclusion, we present some relations between the Chebyshev polynomials of the second kind and generating function for the number of restricted Dyck paths, and connections with the spectral moments of graphs and the Estrada index.