krit.club logo

Algebra - Calculating network pathways-extended

Grade 9IB

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A network pathway involves finding the number of ways to travel from a starting node (usually AA) to a destination node (usually BB) following specific directional rules, such as only moving Right (RR) and Up (UU).

•

Pascal's Method: At any intersection (node) in the grid, the number of ways to reach that node is the sum of the number of ways to reach the nodes immediately preceding it. For a grid where you move Right and Up, the pathways to node (i,j)(i, j) is the sum of pathways to (i−1,j)(i-1, j) and (i,j−1)(i, j-1).

•

Combinatorial Method: In a rectangular grid of size m×nm \times n (where mm is the number of horizontal steps and nn is the number of vertical steps), the total number of pathways is the number of ways to arrange mm 'Rights' and nn 'Ups'. This is calculated as (m+nm)\binom{m+n}{m} or (m+nn)\binom{m+n}{n}.

•

Intermediate Points: If a path must pass through a specific point MM, the total number of pathways from AA to BB via MM is calculated by multiplying the number of paths from AA to MM by the number of paths from MM to BB. Formula: Total=Paths(A→M)×Paths(M→B)Total = Paths(A \to M) \times Paths(M \to B).

•

Restricted Pathways: If a path must avoid a specific point XX, calculate the total paths without restrictions and subtract the paths that pass through XX. Formula: Allowed=Total−(Paths(A→X)×Paths(X→B))Allowed = Total - (Paths(A \to X) \times Paths(X \to B)).

📐Formulae

(nr)=n!r!(n−r)!\binom{n}{r} = \frac{n!}{r!(n-r)!}

Total Paths=(m+n)!m!n!Total \text{ Paths} = \frac{(m+n)!}{m!n!}

Paths(A→B via M)=(xM+yMxM)×((xB−xM)+(yB−yM)xB−xM)Paths(A \to B \text{ via } M) = \binom{x_M + y_M}{x_M} \times \binom{(x_B - x_M) + (y_B - y_M)}{x_B - x_M}

💡Examples

Problem 1:

Determine the number of ways to travel from point A(0,0)A(0,0) to point B(4,3)B(4,3) on a grid, moving only Right and Up.

Solution:

The total number of horizontal steps (mm) is 44 and vertical steps (nn) is 33. Total steps =4+3=7= 4 + 3 = 7. Using the combination formula: (74)=7!4!3!\binom{7}{4} = \frac{7!}{4!3!} 7×6×5×4!4!×(3×2×1)=2106=35\frac{7 \times 6 \times 5 \times 4!}{4! \times (3 \times 2 \times 1)} = \frac{210}{6} = 35

Explanation:

To get from (0,0)(0,0) to (4,3)(4,3), we must make exactly 77 moves. 44 of these must be 'Right'. The number of ways to choose which 44 of the 77 moves are 'Right' is given by the combination formula.

Problem 2:

In a 5×45 \times 4 grid, how many pathways exist from AA to BB that MUST pass through point MM, where MM is 22 units Right and 22 units Up from AA?

Solution:

Step 1: Paths from AA to MM (2 Right, 2 Up): Paths(A→M)=(2+22)=(42)=4×32×1=6Paths(A \to M) = \binom{2+2}{2} = \binom{4}{2} = \frac{4 \times 3}{2 \times 1} = 6 Step 2: Paths from MM to BB. Since BB is at (5,4)(5,4) and MM is at (2,2)(2,2), the remaining steps are 5−2=35-2=3 Right and 4−2=24-2=2 Up: Paths(M→B)=(3+23)=(53)=5×4×33×2×1=10Paths(M \to B) = \binom{3+2}{3} = \binom{5}{3} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10 Total paths =6×10=60= 6 \times 10 = 60.

Explanation:

By the fundamental counting principle, if one event can occur in pp ways and another in qq ways, the sequence of events occurs in p×qp \times q ways. We multiply the pathways of the two sub-grids.