4 ms·

Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?

• xigoi 2y ago
  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.