Make learning comfortable

Visual experienceAnimationRead-aloud speedChanging style, motion, or reading speed keeps your current question, answers, homework, and saved progress. The school band still chooses your task layout. Saved to your learner profile across devices. All lessons and help stay available.

← Introduction to Counting and Probability levels

Introduction to Counting and Probability / LEVEL 2 · DIFFICULTY 2/5

Subsets and Paths

Connect combinations, grids and complements.

3 stages · 24 practice problems · two 6-question assessment forms

Choose an island to read its lesson.

MINI QUEST CP 2.1Unordered SubsetsRead the lesson
MINI QUEST CP 2.2Paths as StringsRead the lesson
MINI QUEST CP 2.3Count the ComplementRead the lesson
LEVEL CHECKCastle challenge
6 questions across this level.
Sign in for the level check →

STAGE CP 2.1 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Unordered Subsets

Useful preparation: Arrangements with Repetition

Goal: Understand and apply unordered subsets.

Before you begin: Arrangements with Repetition

Understand the idea

A subset has no internal order. Counting ordered selections and dividing by the number of orders of each selected group produces the combination formula.

\displaystyle C\, \left(n, r\right) = \frac{n!}{r!\, \left(n - r\right)!}

Choose and carry out a method

Count r distinct selections in order, then divide by $\displaystyle r!$ . Alternatively choose the omitted elements when $\displaystyle n - r$ is smaller.

Check the reasoning

$\displaystyle C\, \left(n, r\right) = C\, \left(n, n - r\right)$ . This symmetry follows because every subset has a unique complement.

WORKED EXAMPLE 1

How many 3-element subsets does a set of 6 distinct elements have?

An unordered selection is counted $\displaystyle 3!$ times by an ordered list.
$\displaystyle C\, \left(6, 3\right) = \frac{6 \cdot 5 \cdot 4}{6}$ .
The count is 20; dividing by 6 removes only order, not valid selections.

WORKED EXAMPLE 2

How many 3-element subsets does a set of 7 distinct elements have?

An unordered selection is counted $\displaystyle 3!$ times by an ordered list.
$\displaystyle C\, \left(7, 3\right) = \frac{7 \cdot 6 \cdot 5}{6}$ .
The count is 35; dividing by 6 removes only order, not valid selections.

Common pitfalls

Possible mix-up: Divide by $\displaystyle n!$ to remove order.

Only the r selected objects are reordered, so divide by $\displaystyle r!$ .

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Why do choosing a committee and choosing its excluded members give equal counts?

Preview the eight practice prompts

Problem 1
How many 3-element subsets does a set of 9 distinct elements have?
Practise this exact problem →
Problem 2
How many 3-element subsets does a set of 10 distinct elements have?
Practise this exact problem →
Problem 3
How many 3-element subsets does a set of 11 distinct elements have?
Practise this exact problem →
Problem 4
How many 3-element subsets does a set of 12 distinct elements have?
Practise this exact problem →
Problem 5
How many 3-element subsets does a set of 13 distinct elements have?
Practise this exact problem →
Problem 6
How many 3-element subsets does a set of 14 distinct elements have?
Practise this exact problem →
Problem 7New context
A library chooses 3 different books from 15 for a display. Their order on the display is ignored. How many selections are possible?
Practise this exact problem →
Problem 8New context
A library chooses 3 different books from 16 for a display. Their order on the display is ignored. How many selections are possible?
Practise this exact problem →

Open stage CP 2.1 in the student workspace →

STAGE CP 2.2 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Paths as Strings

Useful preparation: Unordered Subsets

Goal: Understand and apply paths as strings.

Before you begin: Unordered Subsets

Understand the idea

A shortest right-and-up path is determined by a string of horizontal and vertical moves. Every ordering of the required moves corresponds to exactly one path.

paths=C(

\displaystyle r + u

,r)

Choose and carry out a method

Count the total moves and choose the positions of all right moves. The remaining positions automatically become up moves.

Check the reasoning

A shortest path cannot contain backward moves. Obstacles would invalidate the unrestricted string count and require additional reasoning.

WORKED EXAMPLE 1

How many shortest grid paths go from (0,0) to (4,2) using only right and up unit steps?

Every shortest path is a word with a fixed count of right and up steps.
Choose 4 of 6 step positions for right moves.
There are $\displaystyle C\, \left(6, 4\right) = 15$ paths; each word gives exactly one path.

WORKED EXAMPLE 2

How many shortest grid paths go from (0,0) to (5,2) using only right and up unit steps?

Every shortest path is a word with a fixed count of right and up steps.
Choose 5 of 7 step positions for right moves.
There are $\displaystyle C\, \left(7, 5\right) = 21$ paths; each word gives exactly one path.

Common pitfalls

Possible mix-up: Multiply r by u for the path count.

That counts grid cells, not move orderings.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Write the move string for a path and reconstruct the path from it.

Preview the eight practice prompts

Problem 1
How many shortest grid paths go from (0,0) to (7,2) using only right and up unit steps?
Practise this exact problem →
Problem 2
How many shortest grid paths go from (0,0) to (3,3) using only right and up unit steps?
Practise this exact problem →
Problem 3
How many shortest grid paths go from (0,0) to (4,3) using only right and up unit steps?
Practise this exact problem →
Problem 4
How many shortest grid paths go from (0,0) to (5,3) using only right and up unit steps?
Practise this exact problem →
Problem 5
How many shortest grid paths go from (0,0) to (6,3) using only right and up unit steps?
Practise this exact problem →
Problem 6
How many shortest grid paths go from (0,0) to (7,3) using only right and up unit steps?
Practise this exact problem →
Problem 7New context
A delivery cart must travel 3 blocks east and 4 blocks north without moving backward. How many shortest direction sequences are possible?
Practise this exact problem →
Problem 8New context
A delivery cart must travel 4 blocks east and 4 blocks north without moving backward. How many shortest direction sequences are possible?
Practise this exact problem →

Open stage CP 2.2 in the student workspace →

STAGE CP 2.3 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Count the Complement

Useful preparation: Paths as Strings

Goal: Understand and apply count the complement.

Before you begin: Paths as Strings

Understand the idea

Sometimes the desired set has many overlapping descriptions while its complement is simple. Subtracting the complement from the full sample space avoids those overlaps.

at least one success=all−none

Choose and carry out a method

Count all binary strings, then remove the one with no ones. State clearly why the removed and retained sets partition all possibilities.

Check the reasoning

The complement must use the same string length and restrictions. No outcome may be omitted or subtracted twice.

WORKED EXAMPLE 1

How many binary strings of length 5 contain at least one 1?

Count all outcomes and subtract the unwanted complement.
There are $\displaystyle 2^{5}$ total strings; exactly one has no 1.
The count is $\displaystyle 32 - 1 = 31$ . The complement cases are disjoint.

WORKED EXAMPLE 2

How many binary strings of length 6 contain at least one 1?

Count all outcomes and subtract the unwanted complement.
There are $\displaystyle 2^{6}$ total strings; exactly one has no 1.
The count is $\displaystyle 64 - 1 = 63$ . The complement cases are disjoint.

Common pitfalls

Possible mix-up: Add counts for each possible position of a one.

Strings with several ones would be counted repeatedly.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

When does a condition involving ‘at least one’ suggest using its complement?

Preview the eight practice prompts

Problem 1
How many binary strings of length 8 contain at least one 1?
Practise this exact problem →
Problem 2
How many binary strings of length 9 contain at least one 1?
Practise this exact problem →
Problem 3
How many binary strings of length 10 contain at least one 1?
Practise this exact problem →
Problem 4
How many binary strings of length 11 contain at least one 1?
Practise this exact problem →
Problem 5
How many binary strings of length 12 contain at least one 1?
Practise this exact problem →
Problem 6
How many binary strings of length 13 contain at least one 1?
Practise this exact problem →
Problem 7New context
A controller has 14 independent on/off switches and must have at least one switched on. How many settings are allowed?
Practise this exact problem →
Problem 8New context
A controller has 15 independent on/off switches and must have at least one switched on. How many settings are allowed?
Practise this exact problem →

Open stage CP 2.3 in the student workspace →

Browse another level →