NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← Intermediate Counting and Probability levels

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

Structured Paths and Conditioning

Separate prefix constraints from conditional sample spaces.

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

Choose an island to read its lesson.

  1. MINI QUEST IC 3.1Prefix Constraints and Catalan NumbersRead the lesson
  2. MINI QUEST IC 3.2Conditional Sample SpacesRead the lesson
  3. MINI QUEST IC 3.3Reversing Conditional ProbabilityRead the lesson
  4. LEVEL CHECKCastle challenge

    6 questions across this level.

    Sign in for the level check →

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

Prefix Constraints and Catalan Numbers

Useful preparation: Recurrences from First Choices

Goal: Understand and apply prefix constraints and catalan numbers.

Before you begin: Recurrences from First Choices

Understand the idea

Balanced parentheses require equal final totals and also require every prefix to have at least as many opens as closes. The prefix condition excludes many strings with equal totals.

Cₙ=C(2n,n)/(n+1)

Choose and carry out a method

Count all equal-total strings, then subtract bad strings through a first-crossing reflection correspondence. The difference is C(2n,n)−C(2n,n+1).

Check the reasoning

For one pair the count is one, and for two pairs it is two. A string beginning with a close is invalid regardless of its final totals.

WORKED EXAMPLE 1

How many balanced parenthesis strings have 3 pairs of parentheses?

  1. A valid prefix never has more closes than opens; reflect the first bad prefix to count the complement.
  2. C_3=C(6,3)-C(6,4)=C(6,3)/(4).
  3. The count is 5. Equal final totals alone do not guarantee valid prefixes.

5

WORKED EXAMPLE 2

How many balanced parenthesis strings have 4 pairs of parentheses?

  1. A valid prefix never has more closes than opens; reflect the first bad prefix to count the complement.
  2. C_4=C(8,4)-C(8,5)=C(8,4)/(5).
  3. The count is 14. Equal final totals alone do not guarantee valid prefixes.

14

Common pitfalls

Possible mix-up: Equal numbers of opens and closes guarantee validity.

Every prefix must also keep the open count at least the close count.

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 ()() is valid but )( is not, despite balanced totals.

Preview the eight practice prompts
  1. How many balanced parenthesis strings have 6 pairs of parentheses?
  2. How many balanced parenthesis strings have 7 pairs of parentheses?
  3. How many balanced parenthesis strings have 8 pairs of parentheses?
  4. How many balanced parenthesis strings have 9 pairs of parentheses?
  5. How many balanced parenthesis strings have 10 pairs of parentheses?
  6. How many balanced parenthesis strings have 11 pairs of parentheses?
  7. A stack receives 12 pushes and 12 pops. A pop is forbidden when the stack is empty. How many push/pop patterns obey the rule? New context
  8. A stack receives 13 pushes and 13 pops. A pop is forbidden when the stack is empty. How many push/pop patterns obey the rule? New context
Open stage IC 3.1 in the student workspace →

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

Conditional Sample Spaces

Useful preparation: Prefix Constraints and Catalan Numbers

Goal: Understand and apply conditional sample spaces.

Before you begin: Prefix Constraints and Catalan Numbers

Understand the idea

Conditioning on B means outcomes outside B are no longer possible for the question being asked. The favorable outcomes are those satisfying both A and B.

P(A|B)=P(A∩B)/P(B)

Choose and carry out a method

Restrict the denominator to B and the numerator to A∩B. For equally likely elementary outcomes, divide their counts.

Check the reasoning

P(A|B) and P(B|A) usually have different denominators and need not agree. Conditioning requires P(B)>0.

WORKED EXAMPLE 1

Among 13 outcomes satisfying B, exactly 4 satisfy A as well. There are 21 other outcomes. All outcomes are equally likely. Find P(A|B).

  1. Conditioning restricts the sample space to B.
  2. P(A|B)=|A∩B|/|B|=4/13.
  3. The answer is 4/13; outcomes outside B do not belong in this denominator.

4/13

WORKED EXAMPLE 2

Among 15 outcomes satisfying B, exactly 5 satisfy A as well. There are 22 other outcomes. All outcomes are equally likely. Find P(A|B).

  1. Conditioning restricts the sample space to B.
  2. P(A|B)=|A∩B|/|B|=5/15.
  3. The answer is 1/3; outcomes outside B do not belong in this denominator.

1/3

Common pitfalls

Possible mix-up: Use the whole population in the denominator.

The condition restricts the population to B.

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 the difference between selecting a cyclist and selecting any respondent.

Preview the eight practice prompts
  1. Among 19 outcomes satisfying B, exactly 7 satisfy A as well. There are 24 other outcomes. All outcomes are equally likely. Find P(A|B).
  2. Among 21 outcomes satisfying B, exactly 8 satisfy A as well. There are 25 other outcomes. All outcomes are equally likely. Find P(A|B).
  3. Among 23 outcomes satisfying B, exactly 9 satisfy A as well. There are 26 other outcomes. All outcomes are equally likely. Find P(A|B).
  4. Among 25 outcomes satisfying B, exactly 10 satisfy A as well. There are 27 other outcomes. All outcomes are equally likely. Find P(A|B).
  5. Among 27 outcomes satisfying B, exactly 11 satisfy A as well. There are 28 other outcomes. All outcomes are equally likely. Find P(A|B).
  6. Among 29 outcomes satisfying B, exactly 12 satisfy A as well. There are 29 other outcomes. All outcomes are equally likely. Find P(A|B).
  7. A survey includes 31 cyclists, of whom 13 also swim, plus 30 noncyclists. A respondent is selected uniformly from cyclists. What is the probability they swim? New context
  8. A survey includes 33 cyclists, of whom 14 also swim, plus 31 noncyclists. A respondent is selected uniformly from cyclists. What is the probability they swim? New context
Open stage IC 3.2 in the student workspace →

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

Reversing Conditional Probability

Useful preparation: Conditional Sample Spaces

Goal: Understand and apply reversing conditional probability.

Before you begin: Conditional Sample Spaces

Understand the idea

Observing an outcome changes the relative weights of possible sources. Each source’s updated weight is its prior probability multiplied by the chance of that outcome from that source.

P(A|R)=P(A)P(R|A)/Σₛ P(S)P(R|S)

Choose and carry out a method

Compute the joint weight for every source and the observation. Divide the target source’s weight by the sum of all such weights.

Check the reasoning

The posterior probabilities must add to one. A source with a high observation rate can still have a small posterior if it is rare initially.

WORKED EXAMPLE 1

A box is chosen: box A with probability 4/10, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).

  1. Compare the joint probability for A and red with the total probability of red.
  2. Weights are 4·(1/2) and 6·(1/4); multiply both by 4 to get 8 and 6.
  3. The conditional probability is 8/(8+6)=4/7.

4/7

WORKED EXAMPLE 2

A box is chosen: box A with probability 5/12, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).

  1. Compare the joint probability for A and red with the total probability of red.
  2. Weights are 5·(1/2) and 7·(1/4); multiply both by 4 to get 10 and 7.
  3. The conditional probability is 10/(10+7)=10/17.

10/17

Common pitfalls

Possible mix-up: P(A|R) equals P(R|A).

Reverse conditioning requires prior weights and normalization.

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 does doubling one source’s prior weight change its posterior odds?

Preview the eight practice prompts
  1. A box is chosen: box A with probability 7/16, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  2. A box is chosen: box A with probability 8/18, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  3. A box is chosen: box A with probability 9/20, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  4. A box is chosen: box A with probability 10/22, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  5. A box is chosen: box A with probability 11/24, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  6. A box is chosen: box A with probability 12/26, otherwise box B. P(red|A)=1/2 and P(red|B)=1/4. Given that a red token was drawn, find P(A|red).
  7. Machine A makes 13 batches for every 15 made by B. A batch from A passes a special test with probability 1/2 and one from B with probability 1/4. Given a passing batch, what is the probability it came from A? New context
  8. Machine A makes 14 batches for every 16 made by B. A batch from A passes a special test with probability 1/2 and one from B with probability 1/4. Given a passing batch, what is the probability it came from A? New context
Open stage IC 3.3 in the student workspace →
Browse another level →