I want to make a generalization of Catalan numbers, so I make an $n\times m$ (where $n$ and $m$ are coprime) grid and try to find a number of paths which is not crossing the diagonal.
I think it will be ${2\over n+m} \binom{m+n}{n}$, but I can't find proof of it.
Please help me. Thanks.
Hint: First, count the number of paths which stay above the diagonal, then multiply by $2$.
Write a path as a sequence of $n+m$ steps which are all either $\def\U{\mathsf U}\U$ (for "up") or $\def\R{\mathsf R}\R$ (for "right"). Define the cyclic shift of a path by $k$ places to be the result of removing a block of of $k$ symbols from the beginning and adding them to the end in the same order. $$ \underline{\U\R\R}\U\R\U\U\U\R\implies\U\R\U\U\U\R \underline{\U\R\R}\tag{cyclic shift by 3} $$ Show that among all $m+n$ possible cyclic shifts of a path, exactly one of them will stay above the diagonal. In particular, considering a path as a sequence of points $(x_i,y_i)$, and letting $k$ be the index for which $mx_k-ny_k$ is minimized, then the cyclic shift by $k$ places will be the unique shift which makes the path stay above the diagonal.