Second proof computes Catalan number by removing bad paths (those which touch the forbidden diagonal) from all monotonic paths to compute the number of permitted paths. The proof seems to say that all bad paths are deflected into a different target square, which makes them easy to count. It however insists that there is a bijection between flipped paths and their preimages. Is it important the we can recover the original bad path or it would suffice that we can just pile up all bad paths together?


1 Answer 1


The bijcetion is important to ensure that the count is identical. Every path to $(n-1,n+1)$ can be flipped on its first touch on $y=x+1$ to make a Catalan-forbidden path to $(n,n)$ and vice-versa. So the count of paths to $(n-1,n+1)$ is ${2n\choose n+1}$, selecting where the upward steps occur in the sequence, and this allows the calculation shown in the proof.

  • $\begingroup$ I do not understand how do you explain that there is no other way to ensure that number of votes matches the number of voters other than by bijection. IMO, I see that all reflected paths are deflected into than another target. Why do I need the reversibility? I know that everybody who knocks the door takes a cake. Why should I know who knocked in order to count the cookies? Can I count without bijection? $\endgroup$
    – Val
    Jan 18, 2015 at 11:11
  • 1
    $\begingroup$ @valtih what if there is someone who didn't knock on the door but took a cake anyway? You can only use "door-knockers" to figure out "delta-cake" if you know that the two are the same number. $\endgroup$
    – Joffan
    Jan 18, 2015 at 11:17

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.