Overview

Intermediate counting problems demand structure. Learn to avoid overcounting by using systematic cases and complementary counting.

Key Ideas

• Stars and bars counts nonnegative solutions to $x_1+\cdots+x_k=n$.
• Inclusion-exclusion fixes overlaps: $|A\cup B|=|A|+|B|-|A\cap B|$.
• Symmetry reduces cases by grouping equivalent configurations.

Worked Example

How many nonnegative solutions to $x+y+z=10$ with $x\ge2$?

Let $x'=x-2$. Then $x'+y+z=8$ with nonnegative variables. The answer is $\binom{8+3-1}{3-1}=\binom{10}{2}=45$.

Practice Problems