+0  
 
0
332
2
avatar

Alright, essentially I need to find the number of paths from A to B where the paths you take can only move closer to B.  Just in case you have this text book, it is found on page 94 of iWrite Math Foundations of Mathematics 12. It is lesson #4 Permutations with Repetitions. I am really stuck here, any help is appreciated. 

Guest Mar 27, 2015

Best Answer 

 #1
avatar+20011 
+15

 

 

 

$$nodes:
\begin{array}{ccccccccccc}
A(1) & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4\\
\downarrow && \downarrow && \downarrow && \downarrow & \\
5 & \rightarrow & 6 & \rightarrow & 7 & \rightarrow & 8 & \rightarrow & 9 & \rightarrow & 10 \\
\downarrow && \downarrow && \downarrow && \downarrow && \downarrow && \downarrow \\
11 & \rightarrow & 12 & \rightarrow & 13 & \rightarrow & 14 & \rightarrow & 15 & \rightarrow & 16 \\
\downarrow && \downarrow && \downarrow && \downarrow && \downarrow && \downarrow \\
17 & \rightarrow & 18 & \rightarrow & 19 & \rightarrow & 20 & \rightarrow & 21 & \rightarrow & 22 \\
&&&&&& \downarrow && \downarrow && \downarrow\\
&&&& && 23 & \rightarrow & 24 & \rightarrow & B(25)\\
\end{array}$$

adjacency matrix A:

$$Matrix\ A = \bordermatrix{
nodes & A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & \textcolor[rgb]{1,0,0}{B} \cr
\textcolor[rgb]{1,0,0}{A} &0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&\textcolor[rgb]{1,0,0}{0} \cr
2 &0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
3 &0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
4 &0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
5 &0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
6 &0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
7 &0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0 \cr
8 &0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0 \cr
9 &0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0 \cr
10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0 \cr
11&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0 \cr
12&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0 \cr
13&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0 \cr
14&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0 \cr
15&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0 \cr
16&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0 \cr
17&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0 \cr
18&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0 \cr
19&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0 \cr
20&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0 \cr
21&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0 \cr
22&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1 \cr
23&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0 \cr
24&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1 \cr
B &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
}$$

 $$\small{\text{
entrys $
\qquad 1 = $ one way $\quad 0 = $no way from node x to node y}}$$

$$\textcolor[rgb]{1,0,0}{Matrix \ element[A][B]}$$

$$Matrix\ A^9 =A\cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A = \bordermatrix{
nodes & A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & \textcolor[rgb]{1,0,0}{B} \cr
\textcolor[rgb]{1,0,0}{A} &0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&\textcolor[rgb]{1,0,0}{106} \cr
2 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
3 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
4 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
5 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
6 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
7 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
8 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
9 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
11&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
12&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
13&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
14&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
15&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
16&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
17&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
18&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
19&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
20&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
21&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
22&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
23&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
24&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
B &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
}$$

 

 

A -> B

  $$A^1: \text{ Matrix element[A][B] } =0\quad \text{ (1-station-way)} \\
A*A=A^2: \text{ Matrix element[A][B] } =0 \quad\text{ (2-station-way)} \\
A*A*A=A^3 : \text{ Matrix element[A][B] } =0 \quad\text{ (3-station-way)} \\
A*A*A*A=A^4 : \text{ Matrix element[A][B] } =0 \quad\text{ (4-station-way)}\\
A*A*A*A*A=A^5 : \text{ Matrix element[A][B] } =0 \quad\text{ (5-station-way)} \\
A^6 : \text{ Matrix element[A][B] } =0 \quad\text{ (6-station-way)} \\
A^7 : \text{ Matrix element[A][B] } =0 \quad\text{ (7-station-way)} \\
A^8 : \text{ Matrix element[A][B] } =0 \quad\text{ (8-station-way)}\\
A^9 : \text{ Matrix element[A][B] } =106 \quad\text{ (9-station-way)} \\
A^{10} : \text{ Matrix element[A][B] } =0 \quad\text{ (10-station-way)} \\
etc.: \text{ Matrix element[A][B] } = 0$$

A -> B  (only 9-station ways) = 106

heureka  Mar 28, 2015
 #1
avatar+20011 
+15
Best Answer

 

 

 

$$nodes:
\begin{array}{ccccccccccc}
A(1) & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4\\
\downarrow && \downarrow && \downarrow && \downarrow & \\
5 & \rightarrow & 6 & \rightarrow & 7 & \rightarrow & 8 & \rightarrow & 9 & \rightarrow & 10 \\
\downarrow && \downarrow && \downarrow && \downarrow && \downarrow && \downarrow \\
11 & \rightarrow & 12 & \rightarrow & 13 & \rightarrow & 14 & \rightarrow & 15 & \rightarrow & 16 \\
\downarrow && \downarrow && \downarrow && \downarrow && \downarrow && \downarrow \\
17 & \rightarrow & 18 & \rightarrow & 19 & \rightarrow & 20 & \rightarrow & 21 & \rightarrow & 22 \\
&&&&&& \downarrow && \downarrow && \downarrow\\
&&&& && 23 & \rightarrow & 24 & \rightarrow & B(25)\\
\end{array}$$

adjacency matrix A:

$$Matrix\ A = \bordermatrix{
nodes & A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & \textcolor[rgb]{1,0,0}{B} \cr
\textcolor[rgb]{1,0,0}{A} &0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&\textcolor[rgb]{1,0,0}{0} \cr
2 &0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
3 &0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
4 &0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
5 &0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
6 &0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
7 &0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0 \cr
8 &0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0 \cr
9 &0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0 \cr
10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0 \cr
11&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0 \cr
12&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0 \cr
13&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0 \cr
14&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0 \cr
15&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0 \cr
16&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0 \cr
17&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0 \cr
18&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0 \cr
19&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0 \cr
20&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0 \cr
21&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0 \cr
22&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1 \cr
23&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0 \cr
24&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1 \cr
B &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
}$$

 $$\small{\text{
entrys $
\qquad 1 = $ one way $\quad 0 = $no way from node x to node y}}$$

$$\textcolor[rgb]{1,0,0}{Matrix \ element[A][B]}$$

$$Matrix\ A^9 =A\cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A = \bordermatrix{
nodes & A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & \textcolor[rgb]{1,0,0}{B} \cr
\textcolor[rgb]{1,0,0}{A} &0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&\textcolor[rgb]{1,0,0}{106} \cr
2 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
3 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
4 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
5 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
6 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
7 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
8 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
9 &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
11&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
12&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
13&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
14&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
15&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
16&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
17&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
18&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
19&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
20&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
21&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
22&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
23&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
24&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
B &0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 \cr
}$$

 

 

A -> B

  $$A^1: \text{ Matrix element[A][B] } =0\quad \text{ (1-station-way)} \\
A*A=A^2: \text{ Matrix element[A][B] } =0 \quad\text{ (2-station-way)} \\
A*A*A=A^3 : \text{ Matrix element[A][B] } =0 \quad\text{ (3-station-way)} \\
A*A*A*A=A^4 : \text{ Matrix element[A][B] } =0 \quad\text{ (4-station-way)}\\
A*A*A*A*A=A^5 : \text{ Matrix element[A][B] } =0 \quad\text{ (5-station-way)} \\
A^6 : \text{ Matrix element[A][B] } =0 \quad\text{ (6-station-way)} \\
A^7 : \text{ Matrix element[A][B] } =0 \quad\text{ (7-station-way)} \\
A^8 : \text{ Matrix element[A][B] } =0 \quad\text{ (8-station-way)}\\
A^9 : \text{ Matrix element[A][B] } =106 \quad\text{ (9-station-way)} \\
A^{10} : \text{ Matrix element[A][B] } =0 \quad\text{ (10-station-way)} \\
etc.: \text{ Matrix element[A][B] } = 0$$

A -> B  (only 9-station ways) = 106

heureka  Mar 28, 2015
 #2
avatar+93356 
0

WOW Heureka !    

 

What does "only 9 station ways " refer to?

Melody  Mar 28, 2015

25 Online Users

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.