5
$\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$
  • $\begingroup$ Super-strongly related: math.stackexchange.com/q/33876/23353 $\endgroup$ – apnorton Jan 14 '15 at 23:40
  • $\begingroup$ Hint: It's in the section on Catalan Numbers for a reason! $\endgroup$ – Math1000 Jan 15 '15 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 '15 at 0:33
  • $\begingroup$ Well, just look on Wikipedia and you'll find your answer ;) $\endgroup$ – Math1000 Jan 15 '15 at 14:00
2
$\begingroup$

Check this out for help and a great explanation. http://www-math.mit.edu/~tchow/lattice.pdf

$\endgroup$
  • 1
    $\begingroup$ This should be more of a comment. If you want to include a link, would be nice of you give a synopsis of what the link says. The link is actually quite nice $\endgroup$ – Shailesh Oct 27 '15 at 2:12
1
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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