Counting Paths

• Oct 11th 2007, 05:41 AM
DivideBy0
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 $\displaystyle Pr(Passes through D)=\frac{10\cdot 5}{210}=\frac{5}{21}$

The anwers give $\displaystyle \frac{1}{21}$ please help with what I did wrong!
• Oct 11th 2007, 06:57 AM
Plato
The given answer just makes no sense!
• Oct 11th 2007, 07:04 AM
DivideBy0
Thanks, that's good to know, I've got a test tomorrow on Probability
• Oct 14th 2007, 06:09 PM
ThePerfectHacker
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 $\displaystyle ABCD$ that is simply $\displaystyle 4! = 24$. But what if I have $\displaystyle ABCC$ then the formula is $\displaystyle 4!/1! \cdot 1! \cdot 1! \cdot 2! = 12$.

In general let there be a words consisting of $\displaystyle n_1$ of $\displaystyle a_1$ or $\displaystyle n_2$ of $\displaystyle a_2$, ... $\displaystyle n_m$ of $\displaystyle a_m$ then the number of possible arrangements possible is $\displaystyle \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 $\displaystyle 10$-pule. So for example, $\displaystyle (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 $\displaystyle r$ (right) 6 times and $\displaystyle u$ (up) 4 times. That is $\displaystyle \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, $\displaystyle \frac{5!}{3!\cdot 2!} \cdot \frac{5!}{4!\cdot 1} = 50$.

Thus, the probability is $\displaystyle \frac{50}{210}$.
• Oct 14th 2007, 06:18 PM
tukeywilliams
Yes, the TPH solution involves something called the multinomial coefficient (look at an intro combinatorics book). Or here
• Oct 14th 2007, 06:42 PM
ThePerfectHacker
Quote:

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 $\displaystyle \alpha = (a_1,...,a_n)$ we define $\displaystyle |\alpha| = a_1+...+a_n$ and $\displaystyle \alpha ! = a_1!\cdot ... \cdot a_n!$ where $\displaystyle a_i$ are non-negative integers. And for a vector $\displaystyle \bold{x} = (x_1,...,x_n)$ we define $\displaystyle \bold{x}^{\alpha} = x_1^{a_1}...x_n^{a_n}$.

So we can write,
$\displaystyle (x_1+...+x_n)^{m} = \sum_{|\alpha| = m} \frac{m!}{\alpha!} \bold{x}^{\alpha}$.
(Where $\displaystyle \bold{\alpha} = m$ means all ways of getting components to add up to $\displaystyle m$.)
• Oct 14th 2007, 11:44 PM
DivideBy0
Wow that is a very interesting insight, turning the problem from one using the addition principle to one using the multiplication principle! Wonderful!