Counting: Inclusion–Exclusion & Stars and Bars

Why it works. Follow one element that lies in exactly $k$ of the sets ($k \ge 1$). It is added $k$ times by the singles, subtracted $\binom k2$ times by the pairs, and added back $\binom k3$ times by the triple, for a net count of $k - \binom k2 + \binom k3 = 1$ whether $k$ is $1$, $2$ or $3$. So every element of the union is counted exactly once. The alternating signs are not a patch: they are what makes each element's net contribution $1$.

Spotting it. "None of" is the complement of "at least one of", and "at least one of" is a union: inclusion–exclusion, then subtract from the total.

Step 1. Singles: $\lfloor\tfrac{1000}{2}\rfloor + \lfloor\tfrac{1000}{3}\rfloor + \lfloor\tfrac{1000}{5}\rfloor = 500 + 333 + 200 = 1033$.

Step 2. Pairs (multiples of $6$, $10$, $15$): $166 + 100 + 66 = 332$. Triple (multiples of $30$): $33$.

Step 3. The union has $1033 - 332 + 33 = 734$ elements, so $1000 - 734 = 266$ integers are divisible by none.

Check with the density: a fraction $\tfrac12 \cdot \tfrac23 \cdot \tfrac45 = \tfrac{4}{15}$ of each block of $30$ survives, and $\tfrac{4}{15} \cdot 1000 \approx 266.7$ ✓

Spotting it. Every number in the formula is given except the triple overlap, so inclusion–exclusion is one linear equation.

Step 1. $36$ students play at least one sport, so $36 = 22 + 18 + 15 - 9 - 7 - 6 + x = 33 + x$.

Step 2. $x = 3$.

Check by filling the Venn diagram from the centre out: soccer-and-basketball-only is $9 - 3 = 6$, soccer-and-tennis-only $4$, basketball-and-tennis-only $3$; soccer-only is $22 - 6 - 4 - 3 = 9$, basketball-only $6$, tennis-only $5$. The seven regions add to $36$ ✓

Spotting it. "Uses all three" is hard to count directly (the repeated letters could be anywhere). Its complement, "misses at least one letter", is a union of three simple sets.

Step 1. All strings: $3^5 = 243$. Missing a given letter: $2^5 = 32$, three ways. Missing two given letters: $1$ string, three ways. Missing all three: impossible.

Step 2. Strings missing at least one letter: $3 \cdot 32 - 3 \cdot 1 = 93$.

Step 3. So $243 - 93 = 150$ strings use all three. This is the count of onto functions from $5$ positions to $3$ letters, and the same pattern handles any "every box gets something" question.

Why it works. A distribution of $n$ identical items to $k$ people is the same thing as a row of $n$ stars and $k - 1$ bars: the stars before the first bar go to person $1$, those between the first two bars to person $2$, and so on. Every row gives one distribution and every distribution gives one row, so count rows: choose which $k - 1$ of the $n + k - 1$ positions hold bars. For positive amounts, hand out one each first and distribute the remaining $n - k$.

Spotting it. Lower bounds are handled by paying them up front, which turns the problem back into a plain stars-and-bars count.

Step 1. Put $a' = a - 2$ and $b' = b - 1$. Then $a' + b' + c + d = 9$ with all four nonnegative.

Step 2. $9$ stars and $3$ bars: $\dbinom{12}{3} = 220$.

Spotting it. Stars and bars cannot enforce a CAP directly, but it can count the violators: a variable that is at least $8$ is a lower bound, handled by paying $8$ up front. Then inclusion–exclusion removes them.

Step 1. Without caps: $\dbinom{17}{2} = 136$.

Step 2. Solutions with $x_1 \ge 8$: put $x_1' = x_1 - 8$, so $x_1' + x_2 + x_3 = 7$, giving $\dbinom{9}{2} = 36$. The same for $x_2$ and $x_3$.

Step 3. Two variables cannot both be $8$ or more, since $16 > 15$, so there are no pair corrections. The answer is $136 - 3 \cdot 36 = 28$.

Almost every counting error is choosing the wrong row of that table. The test is two questions: does order matter, and may items repeat? "How many ways to give $10$ identical candies to $4$ children" is unordered with repetition, $\dbinom{13}{3} = 286$; "how many $4$-digit PINs" is ordered with repetition, $10^4$.

BANANA has $\dfrac{6!}{3!\,2!} = 60$ arrangements. Circular arrangements divide by $n$ instead (rotations are the same seating), giving $(n-1)!$, and if reflections also count as the same — a necklace — divide by $2$ more. Every one of those divisions is the same idea: count everything, then divide by the size of the group of motions you are calling identical.

Step 1 — give one to each first; $6$ remain.

Step 2 — distribute the $6$ freely: stars and bars with $n = 4$, $k = 6$ gives $\dbinom{9}{3} = 84$. The "at least one" condition is always handled first, by pre-assigning the minimum and then counting freely.

Spotting it. "Not next to each other" is easiest as a complement: count all seatings, subtract those where they ARE together, and glue the pair into a block for the latter.

Step 1. All circular seatings of $6$: $(6 - 1)! = 120$.

Step 2. Alice and Bob together: treat them as one block, so $5$ units around the table give $(5 - 1)! = 24$ seatings, times $2$ for the order inside the block: $48$.

Step 3. $120 - 48 = 72$.