10
$\begingroup$

This is a question that was asked at the start of the section on Catalan Numbers in my book. I'm having trouble answering it.

My Work

All of the legal paths (ones which do not cross over $y=x$) must begin with a move right and end with a move up. Further, any time the number of upward moves exceeds the number of downward moves, the path becomes illegal. So it would seem, the answer is the total number of paths from $(0,0)$ to $(n,n)$ - (Total illegal paths). The number of paths from $(0,0)$ to $(n,n)$ is $\binom{2n}{n}$. The number of illegal paths I'm slightly less clear on. How do I compute the number of illegal paths?

$\endgroup$
4
  • $\begingroup$ Super-strongly related: math.stackexchange.com/q/33876/23353 $\endgroup$
    – apnorton
    Jan 14, 2015 at 23:40
  • $\begingroup$ Hint: It's in the section on Catalan Numbers for a reason! $\endgroup$
    – Math1000
    Jan 15, 2015 at 0:32
  • $\begingroup$ @Math1000 I don't know what the Catalan Numbers are though. This is my first ever exposure to them. $\endgroup$
    – Dunka
    Jan 15, 2015 at 0:33
  • $\begingroup$ Well, just look on Wikipedia and you'll find your answer ;) $\endgroup$
    – Math1000
    Jan 15, 2015 at 14:00

2 Answers 2

8
$\begingroup$

There are a few ways to solve this question, each of which uses a different, but very useful, counting principle. We wish to count the paths that stay weakly below the line $y=x$ (they can touch the line, but not go above)

1) Reflection Principle

First, we consider the total number of paths that exist from $(0,0)$ to $(n,n)$, which is ${2n}\choose{n}$, since we must take exactly $n$ up steps, each of which we denote by a $u$, and $n$ right steps, each of which we denote by an $r$, and so this simply corresponds to the ${2n}\choose{n}$ ways we can rearrange a string with $n$ $u$s and $n$ $r$s.

Next, we consider the paths that DO go above the line $y=x$ (the bad paths). We note that for each such path, there exists a unique first upstep that brings the path above the line (it could even be the first step). We draw a line of slope $1$ passing through the end of this unique up step, and reflect the path up to that step about the line, giving a path from $(-1,1)$ to $(n,n)$. (See picture)

A bad path reflected after its first bad upstep

Now, we've shown that any bad path can be mapped onto a path from $(-1,1)$ to $(n,n)$. It is indeed true (but you should convince yourself of this) that any path from $(-1,1)$ to $(n,n)$ can be mapped onto a bad path from from $(0,0)$ to $(n,n)$. Hence, there are the same number of bad paths from from $(0,0)$ to $(n,n)$ as the number of all paths from $(-1,1)$ to $(n,n)$, which by the argument above is ${2n}\choose{n-1}$=${2n}\choose{n+1}$.

Hence the number of paths that stay below the line $y=x$ is (after some manipulation): $${{2n}\choose{n}} - {{2n}\choose{n-1}}=\dfrac{1}{n+1}{{2n}\choose{n}}$$

2) Generating Functions

If you are comfortable with generating functions, we can let $g(x)$ be the generating function for paths that stay below the line $y=x$. Let us call paths that stay below the line good paths. Then we can note that each path that is below the line $y=x$ can be broken into two after the first return to the axis. A Dyck path broken into the the part up until the first return to the axis, and another Dyck path

Now if we let $x^{1/2}$ be the weight of each step, then the first part of the path can be written as $x g(x)$, as it is a right step ($x^{1/2}$), followed by a good path ($g(x)$), followed be an up step ($x^{1/2}$). The second part of the path is just another good path ($g(x)$). The only path that cannot be written this way is the lone good path that does not start with a right step, namely, the empty path from $(0,0)$ to $(0,0)$, who's generating series is just $x^0=1$. Hence we have that $$g(x) = x g(x) \cdot g(x)+1=x g(x)^2+1 $$

Solving for $g(x)$ gives: $$g(x) = \dfrac{1 \pm \sqrt{1-4x} }{2x}$$

One can then use the generalized binomial theorem to find the series:

$$g(x) = \sum_{n=0}^{\infty} a_n x^n$$

and you should get $a_n = \dfrac{1}{n+1} {{2n}\choose{n}}$, and of course by our construction, $a_n$ counts the good paths from $(0,0)$ to $(n,n)$.

3) Cycle Lemma

Using the Cycle Lemma (http://www.cs.tau.ac.il/~nachumd/papers/CL.pdf) one can map the good paths from $(0,0)$ to $(n,n)$ to dominating strings of $n+1$ $0$s and $n$ $1$s, where $0$s represent right steps and $1$s represent up steps. The cycle lemma tells us that of the $2n+1$ cyclic permutation of each such possible string, only $(n+1)-n=1$ of them are dominating. and hence since there are ${2n+1}\choose{n}$ possible strings, the total number of dominating strings, which corresponds to the good paths, is:

$$\dfrac{1}{2n+1} {{2n+1}\choose{n}} = \dfrac{1}{n+1} {{2n}\choose{n}}$$

$\endgroup$
0
3
$\begingroup$

Hint: imaging you are counting paths from $(0,1)$ to $(n,n+1)$ that does not touch line $y=x$, quite clearly there is a bijection. Then, all you need to do is to subtract paths that do pass $y=x$ from it. paths that do pass $y=x$ have a bijection with paths from $(1,0)$ to $(n,n+1)$, why?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .