Results 1 to 7 of 7

Math Help - Counting Paths

  1. #1
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432

    Counting Paths

    What is the probability a random journey from A to B passes through the point D? You can only move right or up.

    I got 10 ways from A to D and 5 ways from D to B. I also got 210 ways from A to B.

    Then Pr(Passes through D)=\frac{10\cdot 5}{210}=\frac{5}{21}

    The anwers give \frac{1}{21} please help with what I did wrong!
    Attached Thumbnails Attached Thumbnails Counting Paths-maze.jpg  
    Last edited by DivideBy0; October 11th 2007 at 06:28 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    I agree with your answer. Think about it.
    The given answer just makes no sense!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Thanks, that's good to know, I've got a test tomorrow on Probability
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    This is a little lat but here is my solution.

    First, I am not sure if you know the premutation formula for multiple objects. For example, how many different words can you form with ABCD that is simply 4! = 24. But what if I have ABCC then the formula is 4!/1! \cdot 1! \cdot 1! \cdot 2! = 12.

    In general let there be a words consisting of n_1 of a_1 or n_2 of a_2, ... n_m of a_m then the number of possible arrangements possible is \frac{m!}{(n_1)!\cdot ... \cdot (n_m)!}.

    The above formula is what we will use here. Now in order to go from A to B we need to go 6 times to the right and 4 times up. Thus, we can think of a path as an 10-pule. So for example, (r,r,r,r,r,r,u,u,u,u) represents 6 times to the right and 4 times up in that order. So the question is to determine how many 10-tuples can we form were we use r (right) 6 times and u (up) 4 times. That is \frac{10!}{6!\cdot 4!} = 210.

    Now you need to count the path from A to D and from D to B and multiple there results together to give you the number of path passing through D. That is, \frac{5!}{3!\cdot 2!} \cdot \frac{5!}{4!\cdot 1} = 50.

    Thus, the probability is \frac{50}{210}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Yes, the TPH solution involves something called the multinomial coefficient (look at an intro combinatorics book). Or here
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tukeywilliams View Post
    Yes, the TPH solution involves something called the multinomial coefficient (look at an intro combinatorics book). Or here
    If you are interested in my Real Multidimensional Analysis class we introduced something called "multi-index notation".

    For a vector \alpha = (a_1,...,a_n) we define |\alpha| = a_1+...+a_n and \alpha ! = a_1!\cdot ... \cdot a_n! where a_i are non-negative integers. And for a vector \bold{x} = (x_1,...,x_n) we define \bold{x}^{\alpha} = x_1^{a_1}...x_n^{a_n}.

    So we can write,
    (x_1+...+x_n)^{m} = \sum_{|\alpha| = m} \frac{m!}{\alpha!} \bold{x}^{\alpha}.
    (Where \bold{\alpha} = m means all ways of getting components to add up to m.)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Wow that is a very interesting insight, turning the problem from one using the addition principle to one using the multiplication principle! Wonderful!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of Paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2010, 06:07 AM
  2. Augmenting paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 17th 2009, 04:55 AM
  3. Transversing Paths
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 16th 2009, 08:26 AM
  4. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 07:54 AM
  5. Integration along Paths
    Posted in the Calculus Forum
    Replies: 3
    Last Post: June 6th 2007, 04:35 PM

Search Tags


/mathhelpforum @mathhelpforum