2

I've been trying to solve this problem in my book to no avail:

enter image description here

I am even stuck on part a... to find a closed form of this I started with size 2x2 square, counted the number of paths, then used a 3x3 square, did the same but I feel that was a rather inefficient way to go about doing this problem. Can someone walk me through the solutions for parts (a), (b), (c)? Thanks.

user642796
  • 52,188
user3367265
  • 71
  • Have you learned anything about combinations and binomial coefficients yet? – Brian M. Scott Oct 20 '14 at 06:30
  • You will take $8$ steps, $4$ of them up (U) and $4$ to the right (R). Your path can be described as a word of length $8$ with $4$ U and $4$ R. There are $\binom{8}{4}$ such words. Each path determines a word, and each word determines a path. – André Nicolas Oct 20 '14 at 06:31
  • Hi Scott, I have learned about combinations but not binomial coefficients yet. I tried doing a with 8 C 16 but it won't be valid as it can not combinations of all 8 squares but a special subset which I don't know how to formulate. – user3367265 Oct 20 '14 at 06:31
  • @BrianM.Scott, you can solve the problem without explicitly referring to binomial coefficients, if you notice the relationship between the number of paths to a point and the number of paths to the points directly to the left and directly below (this sum is equivalent to Pascal's rule) – Zubin Mukerjee Oct 20 '14 at 06:36
  • Foe the last problem, the answer is the number of paths there would be without the construction, minus the number of bad paths. which are the paths that go through $(1,4)$. There are just as many of these bad paths as there are paths from $(0,0)$ to $(1,4)$. – André Nicolas Oct 20 '14 at 06:36
  • @Zubin: I’m aware of that; that’s why I asked before suggesting an approach. – Brian M. Scott Oct 20 '14 at 06:37
  • @BrianM.Scott I meant no insult by my comment, I just thought it was worth mentioning :) – Zubin Mukerjee Oct 20 '14 at 06:38
  • @user3367265: Your $8C{16}$ is a binomial coefficient: you just haven’t learned the name yet. But it’s not the one that you want. See André’s first comment: his $\binom84$ is your $_4C8$. – Brian M. Scott Oct 20 '14 at 06:38
  • 1
    @Zubin: Oh, it is, if only for the last part of the question, where that basic idea is surely the easiest way to go! – Brian M. Scott Oct 20 '14 at 06:40
  • Thanks everyone for the replies. I am starting to understand it slowly.. @AndréNicolas your method made the most sense but can you explain in detail what you mean that there are "(8 4) such words." I am confused as to what it means to 8 choose 4. There are 8 letters where 4 are U and 4 are R. So we are choosing only combinations of any 4 letters? Everything about your method makes intuitive sense up until that point. – user3367265 Oct 20 '14 at 06:46
  • 1
    If we are making an $8$-letter "word" with $4$ U and $4$ R, there are $8$ slots to fill. There are $\binom{8}{4}$ ways to choose where the U's will go. Once we have done that, the word is determined, for the rest of the slots have to be filled with R's. What I call $\binom{8}{4}$ is probably what you call ${}_8C_4$, or something like that. It is $\frac{8!}{4!4!}$. – André Nicolas Oct 20 '14 at 06:52
  • The word analogy is still applicable, but becomes a bit difficult, when you try to use it for the third problem. EDIT: @AndréNicolas suggested subtracting the number of bad ways. To see that the number of bad ways is $5$, you can first find the number of ways to get to the point $(1,4)$. – Zubin Mukerjee Oct 20 '14 at 06:53

2 Answers2

0

You can write the number of ways to get to each intersection point while minimizing Taxicab distance by using the fact that the number of paths at any given intersection is equal to the sum of the number of paths that come directly from the left and the number of paths that come directly from below.

enter image description here

You might notice that this looks like Pascal's Triangle turned on its side. That's because it is exactly that. The reason these numbers are equal to binomial coefficients is because the number of paths is exactly the number of ways to arrange the rights and lefts in the path; to get to point $B$ you need $4$ lefts and $4$ rights. There are $$\binom{8}{4}=70$$ ways to choose the order of these rights and lefts.

You should be able to solve the second question using this method.

Good luck :)

EDIT: I've included how the numbers would be assigned for the third part. Notice the $10$ assigned to $(2,4)$.

enter image description here

Zubin Mukerjee
  • 17,832
-1

For part (a), you have in total 8 moves to make, 4 of which has to be up and the other 4 right. You can rearrange the order of these moves in $\binom{8}{4} = 70$ ways. So that is the answer to part (a).

For part (b), you have in total $n+m$ moves to make, n of which has to be up and the other m right. You can rearrange the order of these moves in $\binom{n+m}{n}$ ways.

Calculon
  • 5,725