+0  
 
0
210
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+18845 
+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
Sort: 

2+0 Answers

 #1
avatar+18845 
+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+91517 
0

WOW Heureka !    

 

What does "only 9 station ways " refer to?

Melody  Mar 28, 2015

4 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details