+0

# Help with Permutations with Repetitions?

0
290
2

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

#1
+19480
+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}$$

$$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 & {B} \cr {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&{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}}$$

$${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 & {B} \cr {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&{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
+19480
+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}$$

$$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 & {B} \cr {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&{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}}$$

$${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 & {B} \cr {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&{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
+92623
0

WOW Heureka !

What does "only 9 station ways " refer to?

Melody  Mar 28, 2015