Constrained Counting and Recurrence Workshop

Retrieval Prompts

1. Write the inclusion-exclusion formula for two and three sets.
2. State the generalized pigeonhole principle.
3. Explain why stars and bars is a bijection.
4. Describe the five-step process for deriving a recurrence.

Compare and Distinguish

Separate these methods:

• inclusion-exclusion versus complement counting
• pigeonhole existence proof versus exact counting
• stars and bars versus permutation counting
• recurrence derivation versus recurrence solving

Common Mistake Check

Find the flaw in each:

1. Using stars and bars when the distributed objects are distinct.
2. Writing a recurrence from the first four numerical values alone.
3. Applying inclusion-exclusion without defining the underlying sets.

Mini Application

Do each problem twice: once by describing the model in words, once by computing.

1. Count nonnegative solutions to x1 + x2 + x3 + x4 = 9.
2. Show that among any 9 integers, two have the same remainder modulo 8.
3. Derive a recurrence for ternary strings of length n with no two consecutive equal symbols.
4. Write a generating function for the number of ways to make n using parts of size 1, 2, and 4.

Evidence Check

This page is complete only if your recurrence states include initial conditions and your counting methods are justified before calculation.