[andredurao]

That Project Euler problem was my first encounter with memoization. At the time, it felt like a magical solution, so I ended up solving it using the central column of Pascal's triangle, which was easier for me to understand back then.

I also tried a weird idea involving popcount, but it didn't scale. My approach was to represent each possible path with 0s (don't turn) and 1s (turn), testing the same number of 0s and 1s. However, even with popcount running in O(1) with hardware support, the total number of possible paths made the idea impractical :)

[chatmasta]

The binomial coefficient is derived from Pascal’s triangle, which is a fact I remember but cannot explain, based on some hazy memories of 10th grade math class.

[zmgsabst]

You can take the two variables to be outcomes of a binomial event:

- at zero events: we have one outcome, nothing

- at one event: we have two outcomes, 1X and 1Y

- at two events, each of those two outcomes have two outcomes, but one X and one Y outcome both become XY, so we have 1X^2 2XY 1Y^2.

You can continue combining this way, adding an X and Y to each term (for the two possible outcomes) — and then grouping like terms.