Counting paths with restrictions | Year 11

01 / LEARN

Understand the idea.

Start with a clear counting question

Before counting, specify start, finish, number of edges and repetition rules. A two-edge route has one intermediate vertex. List possibilities systematically by that middle vertex so none is missed or counted twice.

Edge count is separate from travel distance. A direct connection is one step however long it is. A rule forbidding repeated vertices removes branches that revisit an earlier vertex, even if all their arrows exist.

An adjacency power counts walks

For an adjacency matrix, rows give starting vertices and columns give destinations. Entry $a_{i j}$ counts direct connections. In ${(A^{2})}_{i j}$ , each product counts choices through one intermediate vertex; their sum counts all two-edge walks.

More generally, ${(A^{k})}_{i j}$ counts walks of exactly $k$ edges. Repeated vertices remain allowed unless the network prevents them. This interpretation needs entries that count connections, rather than travel-time or distance weights.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Use the middle vertex

Rows and columns are A, B, C. For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , count two-edge walks from A to C.

Worked solution

1
Select the starting row and destination column.
$row A = (0, 1, 1), column C = (\begin{array}{cccccccccc} 1 \\ 1 \\ 0 \end{array})$
The shared positions correspond to intermediate vertices A, B and C.
2
Count choices through each intermediate vertex.
${(A^{2})}_{A C} = 0 (1) + 1 (1) + 1 (0) = 1$
A two-edge walk needs a connection into and out of the same middle vertex.
3
Identify the counted walk.
Only the middle vertex B contributes, giving the single walk A to B to C.

Answer

1 walk.

EXAMPLE 02

Check a no-revisit rule

The edges are A→B, B→A and A→C. Is A→B→A→C a no-repeated-vertex path? Is it a three-edge walk?

Worked solution

1
Check the individual moves.
A to B, B to A and A to C are all supplied directed edges.
2
Test the no-repeat condition.
The sequence visits A at its start and again after returning from B, so it fails the no-repeated-vertex path rule.
3
Count edges and classify the route.
$number of edges = 3$
A walk permits the repeated A, so the sequence is a valid three-edge walk.

Answer

It is not that kind of path, but it is a three-edge walk.

03 / YOUR TURN

Try it yourself.

Check your understanding

If ${(A^{3})}_{P Q} = 4$ , what does 4 mean?

Show answer & reasoning

Four three-edge walks from P to Q.

The exponent three specifies exactly three edges; row P and column Q specify start and finish. The entry four counts four such walks from P to Q.

Keep practising

6 worksheet questions · 12 marks

Open worksheet Worked solutions

Read the questions online

Edges are A→B, A→C, B→D and C→D. List two-edge walks from A to D.
2 marks
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{A A}$ .
2 marks
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{B C}$ .
2 marks
A route must not revisit its start. Why might diagonal entries of $A^{2}$ be excluded from a total?
2 marks
There are two distinct ferry services A→B and three B→C services. Count A→B→C service combinations.
2 marks
Edges are A→B, A→C, B→C, B→D and C→D. List all A-to-D paths with no repeated vertices.
2 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Edges are A→B, A→C, B→D and C→D. List two-edge walks from A to D.
2 marks
B and C are the two possible intermediate vertices.
Each gives one permitted walk.
A→B→D and A→C→D.
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{A A}$ .
2 marks
Row A times column A gives $0 (0) + 1 (0) + 1 (1) = 1$ .
The walk is A→C→A.
1.
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{B C}$ .
2 marks
Row B times column C gives $0 (1) + 0 (1) + 1 (0) = 0$ .
No such two-edge walk exists.
0.
A route must not revisit its start. Why might diagonal entries of $A^{2}$ be excluded from a total?
2 marks
A diagonal entry has identical start and finish.
That violates the no-revisit condition.
They represent walks returning to their starting vertex.
There are two distinct ferry services A→B and three B→C services. Count A→B→C service combinations.
2 marks
There are 2 first-service choices.
Each has 3 second-service choices: $2 (3) = 6$ .
6.
Edges are A→B, A→C, B→C, B→D and C→D. List all A-to-D paths with no repeated vertices.
2 marks
First branch to B or C.
From B choose D or go via C; from C go to D.
A→B→D; A→C→D; A→B→C→D.

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.

Official curriculum source ↗

In this lesson

Understand the idea.

Start with a clear counting question

An adjacency power counts walks

See the method in action.

Use the middle vertex

Select the starting row and destination column.

Count choices through each intermediate vertex.

Identify the counted walk.

Check a no-revisit rule

Check the individual moves.

Test the no-repeat condition.

Count edges and classify the route.

Try it yourself.

Check your understanding

Keep practising