6
$\begingroup$

TL;DR: How is $2\binom{9+12-1}{9-1}$ the number of paths from $(3,0)$ to $(12,12)$ touching or crossing above the diagonal $y=x$?


Full version:

I'm an undergraduate teaching assistant, tutoring discrete maths this year, but I have to admit, I'm struggling to find an explanation for an expression one of my students has come up with in a homework problem (without any logical reasoning)... I hope you can help me see the combinatorial argument!

The exercise in question is:

How many monotonic paths [i.e. the allowed moves from $(x,y)$ are $(x+1,y)$ and $(x,y+1)$] are there from $(3,0)$ to $(12,12)$ that do not touch the diagonal (except for the final move?)

The students know that the number of monotonic paths from $(0,0)$ to $(n,n)$ that do not cross above (but may touch) the diagonal is given by the Catalan number $C_n$.

The most obvious solution is the following:

Introducing an auxiliary subdiagonal $1$ unit length below turns the question into "how many monotonic paths are there from $(1,0)$ to $(12,11)$ that are allowed to touch the diagonal and go through $(3,0)$?"

From $(1,0)$ we can only reach $(2,0)$, from where we can reach $(3,0)$ or $(2,1)$.

There are $C_{11}$ monotonic paths to $(12,11)$ starting from $(1,0)$, and $C_{10}$ starting from $(2,1)$, so the answer is $C_{11}-C_{10}$.

Another valid approach I saw in one submission:

The number of monotonic paths from $(3,0)$ to $(12,11)$ is $\binom{20}{11}$, the number of bad paths (that touch / cross above the diagonal) is $\binom{20}{12}$, so the answer is $\binom{20}{11}-\binom{20}{12}$.

There was no explanation given by the student, but I figured that this expression was most probably derived from André's reflection method, i.e. the number of monotonic paths is $\binom{9+11}{11}$, and if we substitute all $\to$ moves for $\uparrow$ moves and vice versa from the point a path goes bad, we end up at $(11,12)$ instead, which gives us a bijection from the bad paths to all monotonic paths from $(3,0)$ to $(11,12)$, of which there are $\binom{8+12}{12}$. (Fair enough, I would've liked for the student to write down their reasoning, but at least some valid reasoning was not too hard to come up with.)

Now the third approach is the one that I can't wrap my head around, but it leads to the correct answer:

The expression for all monotonic paths from $(3,0)$ to $(12,12)$ is $\binom{9+12}{9}$, the number of bad paths is $2\binom{9+12-1}{9-1}$, so the answer is $\binom{21}{9}-2\binom{20}8$.

No logical reasoning provided at all, so now I'm trying to figure out how the student arrived at this conclusion. I totally see where $\binom{9+12}{9}$ comes from, and at least one of the two occurrences of $\binom{9+12-1}{9-1}$ could be interpreted as the number of monotonic paths from $(3,0)$ to $(11,12)$, all of which are bad paths, but I can't seem to figure out how the remaining bad paths correspond to the expression $\binom{9+12-1}{9-1}$.

$\endgroup$
4
+50
$\begingroup$

As you correctly noted, among all $\binom{9+12}{9}$ possible monotonic paths from $(3,0)$ to $(12,12)\,$, we must exclude the set $S$ of $\binom{9+12-1}{9-1}$ paths from $(3,0)$ to $(11,12)\,$, all of which are necessarily bad. However, this subtraction is not sufficient, because there are other bad paths to be excluded and that are not included in $S$.

To understand this, let us choose at random one of the bad path of $S$ and let us consider the first point in which this path touches the diagonal. We can construct another path that is identical to it until this point, but that is symmetrical to it (with respect to the diagonal) after this point. This new path is clearly bad since it touches the diagonal, and is not included in $S$ because it ends in $(12,11)\,$ and not in $(11,12)\,$. We can repeat this procedure for all paths in $S\,\,$, thus obtaining other $\binom{9+12-1}{9-1}\,$ bad paths to be excluded.

Also note that, since there is a one-to-one correspondence between all bad paths ending in $(12,11)$ and all bad paths ending in $(11,12)$, there cannot be other bad paths. This finally explains the presence of a factor $2$ in the term $\binom{9+12-1}{9-1}$ given in the third solution.

$\endgroup$
  • $\begingroup$ Ouch, guess I missed the forest for the trees - now that you pointed it out, the third solution was really just another way of stating the second solution (for which I had already figured out that the number of bad paths to $(12,11)$ is $\binom{20}{12}=\binom{20}8$...) thanks a lot, you've earned your +50 reputation (which, as Stack Exchange tells me, I can award in 17 hours.) $\endgroup$ – Sora. Dec 1 '17 at 0:33

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.