The number of Dyck paths in a square is wellknown to equal the catalan numbers: http://mathworld.wolfram.com/DyckPath.html But what if, instead of a square, we ask the same question with a rectangle? If one of its sides is a multiple of the other, then again there is a nice formula for the number of paths below the diagonal, but is there a nice formula in general? What is the number of paths from the lowerleft corner of a rectangle with side lengths a and b to its upperright corner staying below the diagonal (except for its endpoint)? I am also interested in asymptotics.

I heard a talk at Indiana University last March by Timothy Chow. Here's his abstract, which seems to give a negative answer to your question about rectangles whose sides have noninteger ratio:



Since that Mirko Visontai told me that the answer is ${a+b\choose a}/(a+b)$ if $\gcd(a,b)=1$. The proof is the following (with k=a and l=b): The number of 01 vectors with $k$ 0's and $l$ 1's is ${k+l\choose k}$, so we have to prove that out of these vectors exactly $1/(k+l)$ fraction is an element of $L(k,l)$. The set of all vectors can be partitioned into equivalence classes. Two vectors $p$ and $q$ are equivalent if there is a cyclic shift that maps one into the other, i.e., if for some $j$, $p_i = q_{i+j}$ for all $i$. We will prove that exactly one element from each equivalence class will be in $L(k,l)$. This proves the statement as each class consists of $k+l$ elements because $gcd(k,k+l)=1$. We can view each 01 sequence as a walk on $\mathbb R$ where each 0 is a $l/(k+l)$ step and each 1 is a $+k/(k+l)$ step. Each $(k,l)$ walk starts and ends at zero and each walk reaches its maximum height exactly once, otherwise $ak + bl = 0$ for some $0 < a +b < k+l$ which would imply $\gcd(k,l) \neq 1$. If we take the cyclic shift that ``starts from the top'', we stay in the negative region throughout the walk, which corresponds to remaining under the diagonal in the lattice path case. Any other cyclic shift goes above zero, which corresponds to going above the diagonal at some point. 


If I understood your question correctly, the numbers you're looking for are called Ballot numbers. The number of paths from (0,0) to (m,n) (where m>n) which stay below the diagonal is \frac{mn}{m+n}\binom{m+n}{m} Moreover, if m>r⋅n, then the number of lattice paths from (0,0) to (m,n) which stay below the line x=r⋅y is \fra{mrn}{m+n}\binom{m+n}{m}. (I haven't worked this out, but Ira Gessel says so in Introduction to Lattice Path Enumeration) 


Is a sum OK? I am used to a different rotation of the paths. I think the paths you are looking for can also be described as all paths above the xaxis, with steps (1,1) and (1,1), that starts at (0,0) and ends on the line x=y+n for some (x,y) from (n,0) to (n+m,m). (If instead they end at the line x=n, we get the Ballot paths.) Let B(n,k) be the Ballot numbers, B(n,k)= # paths from (0,0) to (n,k). Now, all paths must pass the line x=n. From there on it is just a binomial path, so the number of paths are sum_{k=0,2,4,...,n} B(k,n)*( (nmk)/2 choose k/2) (n choose k)= Binomial coefficient, n!/(k!(nk)!) 

