## Dyck paths on rectangles

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

The number of Dyck paths in a square is well-known 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 lower-left corner of a rectangle with side lengths a and b to its upper-right corner staying below the diagonal (except for its endpoint)? I am also interested in asymptotics.

-

2
Can you be more precise about the definition you're using here? Should we take "diagonal" to mean diagonal of the rectangle? – Qiaochu Yuan Oct 22 2009 at 22:18
Yes, the diagonal of the rectangle from its lower-left vertex to its upper-right vertex. – domotorp Oct 22 2009 at 23:47

## 4 Answers

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{m-n}{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{m-rn}{m+n}\binom{m+n}{m}. (I haven't worked this out, but Ira Gessel says so in Introduction to Lattice Path Enumeration)

-

No, this is not what I want. If the sides of the rectangle are 100 and 250, then the ballot numbers would give an answer for a path that stays above the line from (0,0) to (100,200). Btw, this is why I have written that I also know the answer if one side is a multiple of the other. – domotorp Oct 22 2009 at 23:46

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 x-axis, 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)*( (n-m-k)/2 choose k/2)

(n choose k)= Binomial coefficient, n!/(k!(n-k)!)

-

I am afraid that your problem with the 1,1 and 1,-1 steps seems to be different from the one I described. – domotorp Oct 23 2009 at 1:10
No? Take the rectangle, rotate it 45 degrees clockwise so that the diagonal becomes the x-axis, then reflect it in the x-axis.  – Robert Parviainen Oct 23 2009 at 9:49
Then the steps would not be 1,1 and 1,-1 but something depending on a and b. – domotorp Oct 23 2009 at 14:48

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 non-integer ratio:

It is a classical result that if k is a positive integer, then the number of lattice paths from (0,0) to (a+1,b) taking unit north or east steps that avoid touching or crossing the line x = ky is

(a+b choose b) - k (a+b choose b-1).

Disappointingly, no such simple formula is known if k is rational but not an integer (although there does exist a determinant formula). We show that if we replace the straight-line boundary with a periodic staircase boundary, and if we choose our starting and ending points carefully, then the natural generalization of the above simple formula holds. By varying the boundary slightly we obtain other cases with simple formulas, but it remains somewhat mysterious exactly when a simple formula can be expected. Time permitting, we will also describe some recent related work by Irving and Rattan that provides an alternative proof of some of our results.

This is joint work with Chapman, Khetan, Moulton, and Waters.

-
Odd. I would expect that the generating function is algebraic because the corresponding language should be context-free, so I'm surprised nobody's worked it out. – Qiaochu Yuan Oct 23 2009 at 2:07

3
Nice, the full paper is here: www-math.mit.edu/~tchow/lattice.pdf – domotorp Oct 23 2009 at 15:12

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 0--1 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 0--1 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.

-

Sorry for using different variables but it seemed to much work to replace them. Also, I have problems typing tex stuff at mathoverflow because the shortcut buttons prevent me from producing symbols like \ and } on the hungarian keyboard when I answer a question. Surprisingly not when I write a comment. I wonder if anyone had similar problems. – domotorp Jan 19 2010 at 6:02
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9224269986152649, "perplexity_flag": "head"}