Counting Paths

**DivideBy0** · October 11th 2007, 05:41 AM

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!

**Plato** · October 11th 2007, 06:57 AM

I agree with your answer. Think about it.
The given answer just makes no sense!

**DivideBy0** · October 11th 2007, 07:04 AM

Thanks, that's good to know, I've got a test tomorrow on Probability

**ThePerfectHacker** · October 14th 2007, 06:09 PM

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}$ .

**tukeywilliams** · October 14th 2007, 06:18 PM

Yes, the TPH solution involves something called the multinomial coefficient (look at an intro combinatorics book). Or here

**ThePerfectHacker** · October 14th 2007, 06:42 PM

Originally Posted by tukeywilliams

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$ .)

**DivideBy0** · October 14th 2007, 11:44 PM

Wow that is a very interesting insight, turning the problem from one using the addition principle to one using the multiplication principle! Wonderful!

Thread: Counting Paths

LinkBack

Thread Tools

Display

Counting Paths

Similar Math Help Forum Discussions

Number of Paths

Augmenting paths

Transversing Paths

How many paths...?

Integration along Paths

Search Tags