[saucerful]

In case anyone is interested in how to prove "(N + M) Choose (M) paths":

Any such path ends at (N,M). Such a path can be represented as a sequence of N+M bits, 0=right, 1=up, where there are exactly M ups. So choosing a path is identical to choosing the positions of the M ups, thus there are (N+M) choose (M) such paths.

EDIT: My first proof was needlessly complicated because it dealt with paths that ended at arbitrary (N,m) but really you can just let the paths go all the way up to (N,M)-- even if the max value in the list is m < M-- and just ignore the last part of the path. It's still a bijection.