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.

← Intermediate Counting and Probability levels

Intermediate Counting and Probability / LEVEL 2 · DIFFICULTY 2/5

Exclusion, Expectation and Recurrences

Count indirectly and build recursive models.

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

Choose a node to explore its lesson.

MINI QUEST IC 2.1DerangementsRead the lesson
MINI QUEST IC 2.2Indicator VariablesRead the lesson
MINI QUEST IC 2.3Recurrences from First ChoicesRead the lesson
LEVEL CHECKCastle challenge
6 questions across this level.
Sign in for the level check →

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

Derangements

Useful preparation: Upper Bounds by Subtraction

Goal: Understand and apply derangements.

Before you begin: Upper Bounds by Subtraction

Understand the idea

A derangement is a permutation with no object in its original position. Events saying a particular position is fixed overlap, making inclusion–exclusion suitable.

\displaystyle D_{n} = \sum

from

\displaystyle k = 0

\displaystyle n\, \left(-1\right)^{k}\, C\, \left(n, k\right)\, \left(n - k\right)!

Choose and carry out a method

Start with all $\displaystyle n!$ permutations. Alternately subtract and restore choices with specified fixed positions: $\displaystyle C\, \left(n, k\right)\, \left(n - k\right)!$ at step k.

Check the reasoning

For $\displaystyle n = 1$ there are none, and for $\displaystyle n = 2$ there is one. These small cases check the sign and the empty-permutation convention $\displaystyle 0! = 1$ .

WORKED EXAMPLE 1

There are 4 labeled positions. The first 0 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?

Use inclusion-exclusion on the events that a particular object stays fixed.
$\displaystyle D\, \left(4\right) = 4!$ ·( $\displaystyle 1 - \frac{1}{1!} + \frac{1}{2!}$ -… $\displaystyle \frac{+\left(-1\right)^{4}}{4!}$ ).
The derangement count is 9. Fixing k specified positions leaves $\displaystyle \left(4 - k\right)!$ arrangements.

WORKED EXAMPLE 2

There are 5 labeled positions. The first 0 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?

Use inclusion-exclusion on the events that a particular object stays fixed.
$\displaystyle D\, \left(5\right) = 5!$ ·( $\displaystyle 1 - \frac{1}{1!} + \frac{1}{2!}$ -… $\displaystyle \frac{+\left(-1\right)^{5}}{5!}$ ).
The derangement count is 44. Fixing k specified positions leaves $\displaystyle \left(5 - k\right)!$ arrangements.

Common pitfalls

Possible mix-up: Subtract each fixed-position event only once.

Permutations fixing several positions lie in overlapping events and need correction.

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

Explain why choosing k fixed positions leaves $\displaystyle \left(n - k\right)!$ permutations.

Preview the eight practice prompts

Problem 1
There are 7 labeled positions. The first 0 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 2
There are 4 labeled positions. The first 1 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 3
There are 5 labeled positions. The first 1 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 4
There are 6 labeled positions. The first 1 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 5
There are 7 labeled positions. The first 1 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 6
There are 8 labeled positions. The first 1 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?
Practise this exact problem →
Problem 7New context
5 name cards go into matching labeled envelopes. The first 2 cards must be placed correctly and all remaining cards incorrectly. How many assignments are possible?
Practise this exact problem →
Problem 8New context
6 name cards go into matching labeled envelopes. The first 2 cards must be placed correctly and all remaining cards incorrectly. How many assignments are possible?
Practise this exact problem →

Open stage IC 2.1 in the student workspace →

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

Indicator Variables

Useful preparation: Derangements

Goal: Understand and apply indicator variables.

Before you begin: Derangements

Understand the idea

An indicator is one when a particular event occurs and zero otherwise, so its expectation equals the event’s probability. Summing indicators counts successes.

\displaystyle I_{1}

+…

\displaystyle +I_{n}

\displaystyle P\, \left(A_{1}\right)

+…

\displaystyle +P\, \left(A_{n}\right)

Choose and carry out a method

Define one indicator for each trial and add their probabilities. Linearity of expectation does not require the indicators to be independent.

Check the reasoning

Dependence affects distributions and joint probabilities, but not the rule that expectations add. Confirm what one indicator actually measures.

WORKED EXAMPLE 1

A fair die is rolled 9 times. What is the expected number of sixes?

Write the count as a sum of zero-one indicators and add their expectations.
Each indicator has expectation $\displaystyle \frac{1}{6}$ , so E(total)= $\displaystyle \frac{9}{6}$ .
The expectation is $\displaystyle \frac{3}{2}$ . It may be nonintegral even though every actual count is an integer.

$\displaystyle \frac{3}{2}$

WORKED EXAMPLE 2

A fair die is rolled 10 times. What is the expected number of sixes?

Write the count as a sum of zero-one indicators and add their expectations.
Each indicator has expectation $\displaystyle \frac{1}{6}$ , so E(total)= $\displaystyle \frac{10}{6}$ .
The expectation is $\displaystyle \frac{5}{3}$ . It may be nonintegral even though every actual count is an integer.

$\displaystyle \frac{5}{3}$

Common pitfalls

Possible mix-up: Expectations add only for independent events.

Linearity holds even with dependence.

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 can expectation be easier to find than the entire distribution of a count?

Preview the eight practice prompts

Problem 1
A fair die is rolled 12 times. What is the expected number of sixes?
Practise this exact problem →
Problem 2
A fair die is rolled 13 times. What is the expected number of sixes?
Practise this exact problem →
Problem 3
A fair die is rolled 14 times. What is the expected number of sixes?
Practise this exact problem →
Problem 4
A fair die is rolled 15 times. What is the expected number of sixes?
Practise this exact problem →
Problem 5
A fair die is rolled 16 times. What is the expected number of sixes?
Practise this exact problem →
Problem 6
A fair die is rolled 17 times. What is the expected number of sixes?
Practise this exact problem →
Problem 7New context
18 sensors each independently trigger with probability $\displaystyle \frac{1}{6}$ . What is the expected number that trigger on a check?
Practise this exact problem →
Problem 8New context
19 sensors each independently trigger with probability $\displaystyle \frac{1}{6}$ . What is the expected number that trigger on a check?
Practise this exact problem →

Open stage IC 2.2 in the student workspace →

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

Recurrences from First Choices

Useful preparation: Indicator Variables

Goal: Understand and apply recurrences from first choices.

Before you begin: Indicator Variables

Understand the idea

A tiling by lengths one and two begins with exactly one of those tile lengths. Removing the first tile leaves a shorter problem of the same kind.

\displaystyle T_{0} = T_{1} = 1

;

\displaystyle T_{n} = T_{n-1} + T_{n-2}

Choose and carry out a method

Let T(n) count tilings of length n. Use $\displaystyle T\, \left(n\right) = T\, \left(n - 1\right) + T\, \left(n - 2\right)$ , with $\displaystyle T\, \left(0\right) = 1$ and $\displaystyle T\, \left(1\right) = 1$ , and build a table forward.

Check the reasoning

The empty remainder counts as one successful completion. The two first-tile cases are disjoint and exhaustive.

WORKED EXAMPLE 1

How many ways can a row of 5 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?

Classify by the first move or tile: length one or length two.
Let $\displaystyle T\, \left(0\right) = 1$ and $\displaystyle T\, \left(1\right) = 1$ ; then $\displaystyle T\, \left(n\right) = T\, \left(n - 1\right) + T\, \left(n - 2\right)$ .
The recurrence gives $\displaystyle T\, \left(5\right) = 8$ . The empty completion counts once.

WORKED EXAMPLE 2

How many ways can a row of 6 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?

Classify by the first move or tile: length one or length two.
Let $\displaystyle T\, \left(0\right) = 1$ and $\displaystyle T\, \left(1\right) = 1$ ; then $\displaystyle T\, \left(n\right) = T\, \left(n - 1\right) + T\, \left(n - 2\right)$ .
The recurrence gives $\displaystyle T\, \left(6\right) = 13$ . The empty completion counts once.

Common pitfalls

Possible mix-up: An empty board has zero tilings.

There is one way to finish with no tiles left to place.

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

How would allowing a tile of length three change the recurrence?

Preview the eight practice prompts

Problem 1
How many ways can a row of 8 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 2
How many ways can a row of 9 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 3
How many ways can a row of 10 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 4
How many ways can a row of 11 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 5
How many ways can a row of 12 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 6
How many ways can a row of 13 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?
Practise this exact problem →
Problem 7New context
A robot climbs 14 steps using moves of one or two steps. How many different move sequences reach the top exactly?
Practise this exact problem →
Problem 8New context
A robot climbs 15 steps using moves of one or two steps. How many different move sequences reach the top exactly?
Practise this exact problem →

Open stage IC 2.3 in the student workspace →

Browse another level →

Exclusion, Expectation and Recurrences

Derangements

Understand the idea

Choose and carry out a method

Check the reasoning

There are 4 labeled positions. The first 0 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?

There are 5 labeled positions. The first 0 objects must stay in their original positions; every other object must move. How many permutations satisfy these conditions?

Common pitfalls

Explain it to yourself

Indicator Variables

Understand the idea

Choose and carry out a method

Check the reasoning

A fair die is rolled 9 times. What is the expected number of sixes?

A fair die is rolled 10 times. What is the expected number of sixes?

Common pitfalls

Explain it to yourself

Recurrences from First Choices

Understand the idea

Choose and carry out a method

Check the reasoning

How many ways can a row of 5 unit cells be tiled with unit tiles and 1×2\displaystyle 1 \times 21×2 dominoes?

How many ways can a row of 6 unit cells be tiled with unit tiles and 1×2\displaystyle 1 \times 21×2 dominoes?

Common pitfalls

Explain it to yourself

How many ways can a row of 5 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?

How many ways can a row of 6 unit cells be tiled with unit tiles and $\displaystyle 1 \times 2$ dominoes?