[Math] Number of optimal paths through a grid with an ordered path constraint

combinatoricsdiscrete mathematicsgraph theory

I found, but the awesome explanation of Arturo Magidin: Counting number of moves on a grid

the number of paths for an MxN matrix. If I am thinking about this correctly (please say something if I am wrong), but the number of optimal/shortest paths from the lower left corner @ (0,0) to the top right corner @ (m,n) is any path that can be done in m + n moves as we would have to at least move m spaces to the right and n spaces up at some point. If there is no "backtracking" i.e. that there are no allowed moves which are down or left, then all the paths will be of size m + n. Thus the total number of paths from (0,0) to (m,n) is $\binom{m + n – 1}{m}$ or $\binom{m + n -1}{n}$ as we don't care about order and so could transverse in respect to m or n – both lead us to the end point.

The question I am trying to figure out is that when we say we have to move up (at least once) for every move to the right. Thus one move to the right has to be followed by one or moves up. Now I see (or think I see) that we would have the total number of possible paths as above (without cycles or down or left movements) minus those paths which have two right movements RR or above in a row. Thus we could have RUURURUUUR, but nothing such as RUURR…

I don't see how to do this. I am curious of both a straight forward way (combinatorically) as well as the recursive solution if anyone wouldn't mind giving me a hand.

Thanks,

Brian

Best Answer

Wrap RU with duct tape and consider it to be one character; there must be m of these. There must also be n-m U's not preceded by an R. (Hence $n \ge m$.) So there are $$\binom{n}{m} = \binom{n}{n-m}$$ acceptable arrangements.

Related Question