Catalan numbers and reflection principle

304 Views Asked by At

I have the following exercise in Discrete Math: Find the number of paths from $(0, 0)$ to $(7, 9)$ without crossing the line $y = x-3$.

So we've learnt the Reflection method - we take some point on this line function - and start drawing a possible crossing path beyond it, towards the destination ($(7, 9)$). And now we reflect each step we've done from the line towards the destination - and reflect it, such that, if I step upwards to the destination, I reflect this step with right step.

This way, I get some "new destination" - representing our "bad" paths to the real destination. So we subtract the number of paths from $(0, 0)$ to this new destination from the number of all possible paths from $(0, 0)$ to the real destination.

The new destination I've got: $(12, 4)$

The number of all possible paths from $(0, 0)$ to $(7, 9)$: 16 choose 9

The number of all bad paths: (16 choose 4)

The number of legal paths: (16 choose 9) - (16 choose 4)

But, I think it's wrong, so I would be glad if someone can verify it's right and my understanding of this matter is fine.