NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← 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 an island to read its lesson.

  1. MINI QUEST IC 2.1DerangementsRead the lesson
  2. MINI QUEST IC 2.2Indicator VariablesRead the lesson
  3. MINI QUEST IC 2.3Recurrences from First ChoicesRead the lesson
  4. 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.

Dₙ=Σ from k=0 to n (−1)^k C(n,k)(n−k)!

Choose and carry out a method

Start with all n! permutations. Alternately subtract and restore choices with specified fixed positions: C(n,k)(n−k)! at step k.

Check the reasoning

For n=1 there are none, and for n=2 there is one. These small cases check the sign and the empty-permutation convention 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?

  1. Use inclusion-exclusion on the events that a particular object stays fixed.
  2. D(4)=4!·(1-1/1!+1/2!-…+(-1)^4/4!).
  3. The derangement count is 9. Fixing k specified positions leaves (4-k)! arrangements.

9

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?

  1. Use inclusion-exclusion on the events that a particular object stays fixed.
  2. D(5)=5!·(1-1/1!+1/2!-…+(-1)^5/5!).
  3. The derangement count is 44. Fixing k specified positions leaves (5-k)! arrangements.

44

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 (n−k)! permutations.

Preview the eight practice prompts
  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?
  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?
  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?
  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?
  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?
  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?
  7. 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? New context
  8. 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? New context
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.

E(I₁+…+Iₙ)=P(A₁)+…+P(Aₙ)

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?

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

3/2

WORKED EXAMPLE 2

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

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

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
  1. A fair die is rolled 12 times. What is the expected number of sixes?
  2. A fair die is rolled 13 times. What is the expected number of sixes?
  3. A fair die is rolled 14 times. What is the expected number of sixes?
  4. A fair die is rolled 15 times. What is the expected number of sixes?
  5. A fair die is rolled 16 times. What is the expected number of sixes?
  6. A fair die is rolled 17 times. What is the expected number of sixes?
  7. 18 sensors each independently trigger with probability 1/6. What is the expected number that trigger on a check? New context
  8. 19 sensors each independently trigger with probability 1/6. What is the expected number that trigger on a check? New context
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.

T₀=T₁=1; Tₙ=Tₙ₋₁+Tₙ₋₂

Choose and carry out a method

Let T(n) count tilings of length n. Use T(n)=T(n−1)+T(n−2), with T(0)=1 and T(1)=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 1×2 dominoes?

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

8

WORKED EXAMPLE 2

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

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

13

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
  1. How many ways can a row of 8 unit cells be tiled with unit tiles and 1×2 dominoes?
  2. How many ways can a row of 9 unit cells be tiled with unit tiles and 1×2 dominoes?
  3. How many ways can a row of 10 unit cells be tiled with unit tiles and 1×2 dominoes?
  4. How many ways can a row of 11 unit cells be tiled with unit tiles and 1×2 dominoes?
  5. How many ways can a row of 12 unit cells be tiled with unit tiles and 1×2 dominoes?
  6. How many ways can a row of 13 unit cells be tiled with unit tiles and 1×2 dominoes?
  7. A robot climbs 14 steps using moves of one or two steps. How many different move sequences reach the top exactly? New context
  8. A robot climbs 15 steps using moves of one or two steps. How many different move sequences reach the top exactly? New context
Open stage IC 2.3 in the student workspace →
Browse another level →