NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← Intermediate Counting and Probability levels

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

Sets and Distributions

Handle overlaps and constrained allocations.

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

Choose an island to read its lesson.

  1. MINI QUEST IC 1.1Three-Set Inclusion–ExclusionRead the lesson
  2. MINI QUEST IC 1.2Stars and BarsRead the lesson
  3. MINI QUEST IC 1.3Upper Bounds by SubtractionRead the lesson
  4. LEVEL CHECKCastle challenge

    6 questions across this level.

    Sign in for the level check →

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

Three-Set Inclusion–Exclusion

Goal: Understand and apply three-set inclusion–exclusion.

Before you begin: Combinations, elementary probability, binomial coefficients and algebra.

Understand the idea

Adding three set sizes counts members with multiple memberships too often. Subtracting pair intersections fixes double memberships, but triple members then need one final restoration.

|A∪B∪C|=Σ singles−Σ pairs+|A∩B∩C|

Choose and carry out a method

Add single-set counts, subtract all three pair-intersection counts, and add the triple intersection. Pair counts include triple members unless explicitly stated otherwise.

Check the reasoning

Track one member belonging to one, two or three sets. In every case its final contribution to the union must equal one.

WORKED EXAMPLE 1

|A|=21, |B|=19, |C|=17; pairwise intersections AB, AC, BC have sizes 5, 4, 3, and the triple intersection has size 1. Find |A∪B∪C|.

  1. Inclusion-exclusion alternates single, double and triple intersections.
  2. 21+19+17-5-4-3+1.
  3. The union has 46 members. Triple members must be added back after the pairwise subtraction.

46

WORKED EXAMPLE 2

|A|=22, |B|=20, |C|=18; pairwise intersections AB, AC, BC have sizes 6, 5, 4, and the triple intersection has size 2. Find |A∪B∪C|.

  1. Inclusion-exclusion alternates single, double and triple intersections.
  2. 22+20+18-6-5-4+2.
  3. The union has 47 members. Triple members must be added back after the pairwise subtraction.

47

Common pitfalls

Possible mix-up: Pair-intersection counts exclude triple members.

Standard intersection counts include them.

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

Verify the formula by tracking a member who belongs to all three sets.

Preview the eight practice prompts
  1. |A|=24, |B|=22, |C|=20; pairwise intersections AB, AC, BC have sizes 8, 7, 6, and the triple intersection has size 4. Find |A∪B∪C|.
  2. |A|=25, |B|=23, |C|=21; pairwise intersections AB, AC, BC have sizes 9, 8, 7, and the triple intersection has size 5. Find |A∪B∪C|.
  3. |A|=26, |B|=24, |C|=22; pairwise intersections AB, AC, BC have sizes 10, 9, 8, and the triple intersection has size 6. Find |A∪B∪C|.
  4. |A|=27, |B|=25, |C|=23; pairwise intersections AB, AC, BC have sizes 11, 10, 9, and the triple intersection has size 7. Find |A∪B∪C|.
  5. |A|=28, |B|=26, |C|=24; pairwise intersections AB, AC, BC have sizes 12, 11, 10, and the triple intersection has size 8. Find |A∪B∪C|.
  6. |A|=29, |B|=27, |C|=25; pairwise intersections AB, AC, BC have sizes 13, 12, 11, and the triple intersection has size 9. Find |A∪B∪C|.
  7. Three clubs have 30, 28, and 26 members. Their pairwise overlaps (including triple members) are 14, 13, and 12; 10 members attend all three. How many distinct people attend at least one club? New context
  8. Three clubs have 31, 29, and 27 members. Their pairwise overlaps (including triple members) are 15, 14, and 13; 11 members attend all three. How many distinct people attend at least one club? New context
Open stage IC 1.1 in the student workspace →

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

Stars and Bars

Useful preparation: Three-Set Inclusion–Exclusion

Goal: Understand and apply stars and bars.

Before you begin: Three-Set Inclusion–Exclusion

Understand the idea

Placing separators among identical objects encodes a distribution into labeled boxes. Empty boxes correspond to adjacent separators or a separator at an end.

x+y+z=N, x,y,z≥0 ⇒ C(N+2,2)

Choose and carry out a method

To distribute N identical objects into three labeled boxes, arrange N stars and two bars. Choose the two bar positions among N+2 slots.

Check the reasoning

The boxes are labeled but the objects are identical. Positive counts would require placing one object in each box before using the formula.

WORKED EXAMPLE 1

How many nonnegative integer triples (x,y,z) satisfy x+y+z=5?

  1. Arrange stars for objects and separators for labeled groups.
  2. Place two separators among 5+2 positions; adjacent separators allow an empty group.
  3. C(7,2)=21. The objects are identical, while the groups are distinguishable.

21

WORKED EXAMPLE 2

How many nonnegative integer triples (x,y,z) satisfy x+y+z=6?

  1. Arrange stars for objects and separators for labeled groups.
  2. Place two separators among 6+2 positions; adjacent separators allow an empty group.
  3. C(8,2)=28. The objects are identical, while the groups are distinguishable.

28

Common pitfalls

Possible mix-up: Empty boxes are excluded automatically.

Adjacent or end bars represent zero objects and are allowed.

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

Show the star-and-bar string for a distribution containing an empty box.

Preview the eight practice prompts
  1. How many nonnegative integer triples (x,y,z) satisfy x+y+z=8?
  2. How many nonnegative integer triples (x,y,z) satisfy x+y+z=9?
  3. How many nonnegative integer triples (x,y,z) satisfy x+y+z=10?
  4. How many nonnegative integer triples (x,y,z) satisfy x+y+z=11?
  5. How many nonnegative integer triples (x,y,z) satisfy x+y+z=12?
  6. How many nonnegative integer triples (x,y,z) satisfy x+y+z=13?
  7. 14 identical beads are distributed among three labeled trays, possibly leaving some trays empty. How many distributions are possible? New context
  8. 15 identical beads are distributed among three labeled trays, possibly leaving some trays empty. How many distributions are possible? New context
Open stage IC 1.2 in the student workspace →

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

Upper Bounds by Subtraction

Useful preparation: Stars and Bars

Goal: Understand and apply upper bounds by subtraction.

Before you begin: Stars and Bars

Understand the idea

A simple upper bound can be handled by counting all nonnegative distributions and removing those that exceed it. Shifting the offending variable creates an unrestricted smaller problem.

good=all−solutions after x′=x−(b+1)

Choose and carry out a method

For x≤b, subtract solutions with x≥b+1. Replace x by x′+b+1, then apply stars and bars to the reduced total.

Check the reasoning

The bad and good sets partition all solutions. With multiple bounds, overlaps among bad sets require inclusion–exclusion.

WORKED EXAMPLE 1

Count nonnegative integer solutions to x+y+z=6 with x≤3.

  1. Count unrestricted distributions, then subtract those violating the upper bound.
  2. For x≥4, set x′=x-4. Subtract C(4,2) from C(8,2).
  3. There are 22 allowed distributions. A shift by 3 would incorrectly exclude the boundary.

22

WORKED EXAMPLE 2

Count nonnegative integer solutions to x+y+z=7 with x≤3.

  1. Count unrestricted distributions, then subtract those violating the upper bound.
  2. For x≥4, set x′=x-4. Subtract C(5,2) from C(9,2).
  3. There are 26 allowed distributions. A shift by 3 would incorrectly exclude the boundary.

26

Common pitfalls

Possible mix-up: Subtract cases with x≥b.

The bound allows x=b; bad cases begin at b+1.

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 does subtracting b+1 from x preserve a one-to-one correspondence?

Preview the eight practice prompts
  1. Count nonnegative integer solutions to x+y+z=9 with x≤3.
  2. Count nonnegative integer solutions to x+y+z=10 with x≤3.
  3. Count nonnegative integer solutions to x+y+z=11 with x≤3.
  4. Count nonnegative integer solutions to x+y+z=12 with x≤3.
  5. Count nonnegative integer solutions to x+y+z=13 with x≤3.
  6. Count nonnegative integer solutions to x+y+z=14 with x≤3.
  7. 15 identical counters are placed in three labeled cups, but the first cup holds at most 3. How many distributions are allowed? New context
  8. 16 identical counters are placed in three labeled cups, but the first cup holds at most 3. How many distributions are allowed? New context
Open stage IC 1.3 in the student workspace →
Browse another level →