1
$\begingroup$

I'm currently working on a problem involving path counting in the $x-y$ plane, and I could use some guidance on how to approach it. The problem is as follows:

enter image description here

My approach to solving (a) was that we start at the point $(0,3)$ and need to reach the point $(7,2). In each step, we can either move up one unit and to the right one unit (denoted as U), or move up one unit and to the left one unit (denoted as L). To reach our destination, we must take 3 "U" steps and 4 "L" steps. This is because we need to go from a starting y-coordinate of 3 to a final y-coordinate of 2 (a difference of 1), and move 7 units in the x-direction. Now, the question is how many different combinations of 3 "U" steps and 4 "L" steps we can take, where the order of the steps doesn't matter. To count these combinations, we can use combinatorics. One way to do this is by calculating the binomial coefficient "7 choose 3," which is also denoted as "C(7,3)." This can be computed as: C(7,3) = 7! / (3!(7-3)!) = 35.

But I am not sure if this correct?

As for (b) to (d), I am not really sure how to solve the questions and would like some help.

$\endgroup$
6
  • 1
    $\begingroup$ "Up and right" or "Up and left" You mean Right and up... versus Right and down. Recall that the first entry is the x-position (right vs left) and the second entry is the y-position (up vs down). I would call these "U" moves and "D" moves... I have no idea why the book would have chosen to call the other type "L". $\endgroup$
    – JMoravitz
    Commented Sep 5, 2023 at 13:29
  • $\begingroup$ For (A) this is correct. For (B)-(D) you can read more about the generalized method on the wiki page for bertrand's ballot theorem. See also Catalan numbers. $\endgroup$
    – JMoravitz
    Commented Sep 5, 2023 at 13:31
  • $\begingroup$ So for (B), we can think of "U" moves as votes for candidate "Up" and "D" moves as votes for candidate "Down." We have 3 votes for "Up" and 4 votes for "Down" to distribute in any order. Applying Bertrand's Ballot Theorem, the number of paths that touch or cross the x-axis at least once is given by: $$\frac{{3 - 4}}{{3 + 4}} \binom{{3 + 4}}{{3}} = \frac{{-1}}{{7}} \binom{{7}}{{3}}$$ Whereby we need to take the absolute value of this result since we're interested in the number of paths. This will give us the count of such paths? $\endgroup$
    – Bryan C
    Commented Sep 5, 2023 at 13:38
  • $\begingroup$ The method was shared in the link, not the result. Note that with the typical formulation of the bertrand ballot problem both candidates start with zero votes. Here, it is as though your "U" candidate started with a guaranteed lead of three votes. Clearly, a negative number can not be the answer to a counting problem. $\endgroup$
    – JMoravitz
    Commented Sep 5, 2023 at 13:42
  • $\begingroup$ @JMoravitz I apologize for the oversight and any confusion caused. You are absolutely correct, and I appreciate your clarification. You're right that in the typical formulation of Bertrand's Ballot Problem, both candidates start with zero votes. In this problem, it's not a classical ballot problem, and I misspoke in my previous response. Correcting my mistake, we'll have: 3 votes for "Up" and 4 votes for "Down," but both candidates start with zero votes. Therefore, we should consider the paths where "Down" (D) moves take the lead at some point. To count these paths, we can use combinatorics. $\endgroup$
    – Bryan C
    Commented Sep 5, 2023 at 13:47

1 Answer 1

Reset to default
1
$\begingroup$

Your answer for (A) is correct.

For (B) and the rest, imagine a red line at $y=0$

enter image description here

A path which starts at $(0,3)$ and ends at $(7,2)$ who touched or crossed this red line corresponds uniquely to a path which starts at $(0,3)$ and ends at $(7,-2)$ and can be found by reflecting the path across the red line from that point where it first touched the red line. The pictured path having touched at $(3,0)$ will correspond to the new path in blue.

enter image description here

Indeed, one can prove that every path from $(0,3)$ to $(7,-2)$ corresponds to such a "reflected" path, which then corresponds uniquely to paths from $(0,3)$ to $(7,2)$ which touched or crossed the $x$-axis.

The answer to (B) is then the same as the number of paths from $(0,3)$ to $(7,-2)$

This is formed by one $U$ moves and six $D$ moves (or L moves if you prefer) in any order, for a total of $\binom{7}{1}=7$ such paths

For (C) the number of "good" paths is simply the total number of paths minus the number of "bad"

For (D), generalize the result to larger arbitrary numbers.

$\endgroup$
4
  • $\begingroup$ So the number of paths from (0,3) to (7,-2) we write it as $\left(\begin{array}{c}(7-0)+(-2-3) \\ (-2-3)\end{array}\right)$? I took the formula from here. math.stackexchange.com/questions/2250966/… $\endgroup$
    – Bryan C
    Commented Sep 5, 2023 at 14:15
  • $\begingroup$ @BryanC no. You will not have a negative number as the second argument in the binomial coefficient. We will have $7$ spaces (found by looking at $7-0$, the difference in the $x$-coordinates). We will within the seven spaces have some number of $U$'s and some number of $D$'s such that we have $-2-3=-5$ more $U$'s than $D$'s... (i.e. we have $5$ more $D$'s than $U$'s) which you can see means we have six $D$'s and one $U$ $\endgroup$
    – JMoravitz
    Commented Sep 5, 2023 at 14:19
  • $\begingroup$ Subtracting the number of "bad" paths (those that do touch or cross the x-axis) from the total number of paths. In part (A) the total number of paths from $(0,3)$ to $(7,2)$ is $\binom{7}{3} = 35$. In part (B), we found that the number of "bad" paths (those that touch or cross the x-axis) is 7. Number of "good" paths = Total paths - Number of "bad" paths = 35 - 7 = 28. So, there are 28 paths from $(0,3)$ to $(7,2)$ that never touch or cross the x-axis, and this answer is derived by subtracting the number of "bad" paths from the total number of paths. (Assuming <7, 1> was ans for (b)) Correct? $\endgroup$
    – Bryan C
    Commented Sep 5, 2023 at 14:20
  • $\begingroup$ @BryanC be careful copying formulas that are used for other similar but different problems. The formula you tried to cite looks like it was talking about moving straight up, or straight right. Our motions here are diagonal up-right, and diagonal down-right. In the end, the methods by which you find the formulas are what should be learned, not the formulas themselves. $\endgroup$
    – JMoravitz
    Commented Sep 5, 2023 at 14:21

You must log in to answer this question.

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