Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Dyck paths count paths from $(0,0)$ to $(n,n)$ in steps going east $(1,0)$ or north $(0,1)$ and that remain below the diagonal.

How many of these pass through a given point $(x,y)$ with $x \leq y$?

enter image description here

share|improve this question
4  
How many paths from $(0,0)$ to $(x,y)$ (standard formula)? For each of these, how many ways to get to $(n,n)$ (mild adaptation of standard formula)? –  André Nicolas Sep 15 '11 at 2:39
4  
Note that the actual definition of a Dyck path requires that the path remain below the diagonal line. However, Andre's hint is still good. The formula is slightly less standard, so I'll give you a reference: kasadkad.wordpress.com/2009/03/22/dyck-paths –  David Speyer Sep 15 '11 at 2:49
2  
Do you really mean $x\le y$? If a Dyck path passes through $(x,y)$, and $x\le y$, then $x=y$. –  Brian M. Scott Sep 15 '11 at 3:46
    
thanks David and Andre. Is this the same as Gessel-Viennot? –  john mangual Sep 15 '11 at 15:20
add comment

2 Answers 2

up vote 3 down vote accepted

Just to get an answer on record ...

Let $d_n$ be the number of Dyck paths from the origin to $(n,n)$.

Assuming that the question is worded correctly: As I noted in my comment, if a Dyck path passes through a point $(x,y)$ with $x \le y$, then in fact $x=y$, and the path is the concatenation of a Dyck path from the origin to $(x,x)$ and another from $(x,x)$ to $(n,n)$. (By a Dyck path from $(x,x)$ to $(n,n)$ I mean a path of unit steps east or north that never rises above the diagonal.) There are $d_x$ Dyck paths from the origin to $(x,x)$ and $d_{n-x}$ from $(x,x)$ to $(n,n)$, so $d_xd_{n-x}$ of the $d_n$ Dyck paths from $(0,0)$ to $(n,n)$ go through $(x,x)$.

If you already know that $d_n = \dfrac{1}{n+1}\dbinom{2n}{n} = C_n$, the $n$-th Catalan number, you can immediately conclude that the desired number is $$\frac{1}{(x+1)(n-x+1)}\binom{2x}{x}\binom{2(n-x)}{n-x}.$$

If not, you can at least get a nice recurrence for the $d_n$, though it takes some ingenuity. Let $e_n$ be the number of Dyck paths from $(0,0)$ to $(n,n)$ that hit the diagonal only at those two points. Each of these must start with a move from $(0,0)$ to $(1,0)$ and end with a move from $(n,n-1)$ to $(n,n)$, and between $(1,0)$ and $(n,n-1)$ they must never rise above the line $y=x-1$. A little thought reveals that there are exactly as many of these paths as there are Dyck paths from $(0,0)$ to $(n-1,n-1)$, so $e_n=d_{n-1}$.

Now let $D_n$ be the set of Dyck path from $(0,0)$ to $(n,n)$. For $k=1,2,\dots,n$ let $D_n(k)$ be the set of Dyck paths in $D_n$ whose first intersection with the diagonal after $(0,0)$ is at $(k,k)$; clearly $D_n =$ $\bigcup\limits_{k=1}^nD_n(k)$. There are $e_k$ Dyck paths from $(0,0)$ to $(k,k)$ that don’t hit the diagonal between these two points, and there are $d_{n-k}$ from $(k,k)$ to $(n,n)$, so $\vert D_n(k)\vert = e_kd_{n-k} = d_{k-1}d_{n-k}$. It follows that $$d_n = \vert D_n\vert = \sum\limits_{k=1}^n d_{k-1}d_{n-k} = \sum\limits_{k=0}^{n-1} d_kd_{n-1-k}.$$ Replacing $n$ by $n+1$ and noticing that $d_0=1$, we can write this recurrence as $$\begin{align*}d_0 &= 1,\\ d_{n+1} &= \sum\limits_{k=0}^n d_kd_{n-k},\end{align*}$$ which is sometimes taken to be the definition of the Catalan numbers.

If $\bf x \le y$ is supposed to be $\bf x\ge y$, the question is substantially harder. In fact, I’ve found no way to get a reasonably nice answer that isn’t simply a generalization of a standard proof that the number of Dyck paths from the origin to $(n,n)$ is $\dfrac{1}{n+1}\dbinom{2n}{n}$. The reflection argument in this link mentioned by David Speyer is the obvious choice.

It shows that the number of paths from the origin to $(x,y)$ that don’t rise above the diagonal is $$\frac{x+1-y}{x+1}\binom{x+y}{x}.$$ Each of these can be combined with any path from $(x,y)$ to $(n,n)$ that doesn’t rise above the diagonal, so the next step is to count these paths. Imagine following one of them backwards, from $(n,n)$ to $(x,y)$: you must take $n-y$ steps south and $n-x$ steps west, and you must never have taken more steps west than south (or else you’d cross the diagonal). There are exactly as many ways to do that as there are to start at the origin and take $n-y$ steps east and $n-x$ steps north, making sure never to have taken more steps north than east. But those are just the paths from the origin to $(n-y,n-x)$ that never rise above the diagonal, so there are $$\frac{(n-y+1)-(n-x)}{n-y+1}\binom{(n-y)+(n-x)}{n-y} = \frac{x+1-y}{n+1-y}\binom{2n-x-y}{n-y}$$ of them.

The grand total of paths from the origin through $(x,y)$ to $(n,n)$ that never rise above the diagonal is therefore

$$\begin{align*} &\frac{x+1-y}{x+1}\binom{x+y}{x} \cdot \frac{x+1-y}{n+1-y}\binom{2n-x-y}{n-y} =\\ &\frac{(x+1-y)^2}{(x+1)(n+1-y)} \binom{2n-(x+y)}{n-x} \binom{x+y}{x}. \end{align*}$$

It may be of some small interest to note that the factor $$\dbinom{2n-(x+y)}{n-x} \dbinom{x+y}{x}$$ is the total number of monotone paths from the origin to $(n,n)$ by way of $(x,y)$. Thus, the fractional multiplier can be thought of as the probability that if one of these paths is chosen at random (with uniform distribution), it will not rise above the diagonal.

share|improve this answer
add comment

There are in total ${x+y \choose x}$ paths from $(0,0)$ to $(x,y)$; the proportion of this which stay strictly below the diagonal (except at the start) is $\frac{x-y}{x+y}$ by the Ballot theorem. Similarly there are in total ${2n-x-y \choose n-x}$ paths from $(x,y)$ to $(n,n)$ of which the proportion $\frac{(n-y)-(n-x)}{(n-y)+(n-x)}$ would have stayed strictly below the diagonal (except at the end). So the number of paths from $(0,0)$ to $(n,n)$ via $(x,y)$ which stay strictly below the diagonal is $$\left( \frac{x-y}{x+y} \right) \left(\frac{x-y}{2n-x-y} \right) {x+y \choose x} {2n-x-y \choose n-x}.$$

To translate these into paths below or touching the diagonal, we simply chop off the first horizontal step and last vertical step, so have to replace $x$ by $x+1$ and $n$ by $n+1$, while leaving $y$ alone. So the number of paths becomes

$$\left( \frac{x-y+1}{x+y+1} \right) \left(\frac{x-y+1}{2n-x-y+1} \right) {x+y+1 \choose x+1} {2n-x-y+1 \choose n-x}$$

which looks rather like Brian's answer and is in fact the same.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.