An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed.
You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!]
[1] https://brilliant.org/wiki/permutations-with-repetition/
The way I thought about it: to get to the goal you have to do 20 steps: 10 times right, 10 times down. But the order of these steps does not matter, ever possible arrangement is a solution.
So for counting, you can basically think about it as a list of twenty initially empty spots. You first fill it in with your 10 down steps. The remaining 10 spots will then be the ones for the 10 right steps. So really the only choice you have to make is where to place the 10 down steps.
This question boils down to: in how many different ways can you distribute the 10 down steps over the 20 empty spots? That's 20 choose 10.
Just noticed this, but intriguingly, Catalan numbers are (2n C n)/(n+1), which hints at a connection with trees.
Off the cuff, notice that the diagonal has n+1 intersection points, and a path that never passes through the diagonal gives a forest via the isomorphism with ballot sequences [0]. Any sequence that does pass below the diagonal can be "rotated" into one that doesn't, and so there are probably n+1 paths in each "path class" on average.
Conversely, this would suggest that all paths contained in just one upper or lower triangle of the square can be counted by the Catalan numbers. Indeed, a 2x2 square has just 2 such paths and (2n C n)/(n+1) = 6/3 = 2.
[0]:https://blog.wilsonb.com/posts/2026-02-27-easy-random-trees....
Funny, but I've recently started a blog to keep my math and physics muscles working and this exact problem is the first post I've written - it is useful in high order perturbation theory in quantum mechanics that I'm planning to describe down the line. Counting these paths is cool problem but generating all of them was more challenging.
Anyway, here is the post https://kpatucha.github.io/posts/Dyck-paths-Raneys-lemma/
This was one of my favorite Project Euler problems, but getting to the mathematical solution admittedly took me a couple of weeks.
Perhaps because I was pigeon-holing this as a programming optimization problem.
I wrote about it too! [0]
[0] https://nmn.gl/blog/vibe-coding-gambling
or just rotate it by 45 degrees and pretend it's a pascal's triangle.