0
$\begingroup$

The problem reads (Martin: The art of enumerative combinatorics, problem 1.11.2):

How many shortest paths, consisting only of nonoverlapping (except at endpoints) unit segments that are parallel to an axis, are there from the origin in the plane to the point $(10, 6)$?

My question is for what is really asking the problem, not the answer of it. If I want to go from the origin to the grid-point $(10,6)$ without overlapping I have to begin either with a step to the right $R$, or up $U$, and end in a similar way. Thus, I have $\frac{14!}{9! 5!}$ to travel starting from, say starting with $R$ and ending with $U$ (Notice that I cannot start, e.g. with $U$ and end with $U$, because any other path will have an intersection with this path).

Actually, I think that the only allowed combinations to start and end are the tuples $(R,U)$ and $(U,R)$, each one of them with $\frac{14!}{9! 5!}$ ways to travel from the origin to the destination point.

So at the end I'm confused of what to count, if pairs of allowed paths (possibly repeated) or what?

$\endgroup$
4
  • $\begingroup$ You can start with an $U$ and end with an $U$. You want to find all shortest paths $p$ such that: $p$ starts at $(0,0)$ and ends at $(10,6)$, $p$ can only move up or right with distance $1$ and $p$ does not cross itselfs. $\endgroup$
    – Hetebrij
    Commented Dec 3, 2015 at 20:17
  • 1
    $\begingroup$ I think you're misreading, and getting hung up on, the word "nonoverlapping". It's the unit steps in a path that are not allowed to overlap in this problem. There is no condition that different paths be nonoverlapping. (I don't actually understand why the author felt it necessary to state that the steps in paths be nonoverlapping. The only way I can see for steps to overlap is for either backtracking or a cycle to occur, and both of these are ruled out by the condition that the path be a shortest path.) $\endgroup$
    – Will Orrick
    Commented Dec 3, 2015 at 20:29
  • $\begingroup$ @WillOrrick So you say that the overlapping condition holds for the path itself, and not for two different paths? If this is the case, then the possible paths will just be $\frac{16!}{10! 6!}$ $\endgroup$
    – user2820579
    Commented Dec 3, 2015 at 21:44
  • $\begingroup$ Yes, that's my reading of the problem. $\endgroup$
    – Will Orrick
    Commented Dec 4, 2015 at 2:38

1 Answer 1

Reset to default
1
$\begingroup$

You are on the right path, but off by $1$ a couple places. You need $16$ steps, of which $10$ are $R$ and the other $6$ are $U$, so you just choose $10$ of the steps to be $U$, getting ${16 \choose 10}$. There are no other restrictions.

$\endgroup$
2
  • $\begingroup$ It confuses me the non-overlapping condition. If I ignore it I know that the answer is $\frac{16!}{10!6!}$ for all possible ways to got from the origin to the destination taking always $10$ steps to the right and $6$ steps up. $\endgroup$
    – user2820579
    Commented Dec 3, 2015 at 21:48
  • $\begingroup$ Once you specify the segments are axis aligned and allow the endpoints to be common, the non-overlapping does not matter. If you had any overlap, you would have to be going down or left on one of the segments and the path would be longer. $\endgroup$
    – Ross Millikan
    Commented Dec 3, 2015 at 22:39

You must log in to answer this question.

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