0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Is the constraint that every R must be followed by a U, or that the total number of R's must be less than or equal to the total number of U's. If the former, the previous analysis can be modified to fit. If the latter, look up Dyck Paths, the wikipedia article on Catalan numbers is a good place to start. $\endgroup$
    – deinst
    Jul 19, 2013 at 13:21
  • $\begingroup$ I edited the question to make it clearer. In answer though, ever move to the right HAS to be followed by one or more ups. The number of R's don't have to be less than or equal to the U's, this all depends on the rectangular grid i.e. if the grid is longer vertically than horizontally then U's will be more than the number of R's, but if the grid is wider than tall we will have more R's. $\endgroup$
    – Relative0
    Jul 19, 2013 at 13:32
  • $\begingroup$ Shouldn't the number of paths from (0,0) to (m,n) be C(m+n,m) or C(m+n,n)? (Drat, I can't get LaTex to work for me.) $\endgroup$
    – awkward
    Jul 19, 2013 at 13:35

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ +1 Duct tape fixes all your problems. $\endgroup$
    – Calvin Lin
    Jul 20, 2013 at 18:37
1
$\begingroup$

Let $m$ be the horizontal direction and $n$ be the vertical direction.

If $m>n+1$, there are no such paths since there will always be at least one set of $RR$s in the path.

Since each R must have a U between, we can always start with at least $RURU...URUR$ as a pattern. Thus, we need at least $m-1$ $U$ moves.

The "surplus" can be arranged any way we see fit. Then there are $\Big(\binom{n-m+1}{n+1}\Big)$ ways of arranging your "extra" $U$ moves between the $R$ moves - or before the first $R$ move or after the last $R$ move, where $\Big(\Big(.\Big)\Big)$ is the notation for the multiset coefficient.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .