3 ms·

You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.

• philiplu 2y ago
  Something this illustrates, though - once you solve a problem, read the forum thread (the link will be at the bottom of the problem page when solved). I learned so much poring over the solutions of earlier solvers. Without that knowledge, there's no way I could have gotten lots of later problems. Sure, problem #15 is very early and I happened to know the answer right off, back the first day I started solving PE problems. But even so, there are some gems in the posts from other solvers.
• fallingknife 2y ago
  On second look I think it can be further generalized to N+M nCr M for all grids NxM where N >= M since the number of ways should depend on combinations of the smaller number.
• nonameiguess 2y ago
  I'm a bit disappointed I didn't see this quicker back when I did this problem like 15 years ago or whatever it is now. My solution was to use matrix exponentiation on the adjacency matrix of the path graph, which is a heck of a lot better than brute force enumeration of all paths, but still roughly cubic rather than linear like computing a bunch of factorials. Even as a math major, I'd done a lot more linear algebra than combinatorics.