Discrete - test 1 prep

"and" / do this then that

Multiplication rule

Sequential choices, filling distinct slots, building something step by step.
License plate (letter, letter, number...), president then VP then treasurer.
Multiply the choices at each stage.

"at least one" / "none" / "not"

Complement
"At least one of each color", "at least 2 women", "no consecutive letters"

"or" between non-overlapping cases

Addition rule

You split into cases that can't happen at the same time, then add.
The treasurer-gender split is this: male-treasurer case + female-treasurer case.

"at least k" with a small k

Complement or casework

"At least 2 women" = total − (0 women) − (1 woman).
"At least 3 heads" = 1 − P(0) − P(1) − P(2).
Small k means few cases to subtract.

"arrange" / "line up" / "order" / "in a row"/ distinct roles

Permutation

Order matters, or swapping two items gives a different outcome.

"choose" / "select" / "team" / "committee" / "group" / "subset" / "hand"

Combination

Order doesn't matter — a team of {A,B} is the same as {B,A}.
This is your default for "pick k out of n" with no roles attached.

"identical balls into boxes" / "x1 + x2 + ... = n" / "how many of each type"

Stars and bars

You care about counts per category, not which specific item.
Cans of soda, marbles by color, integer solutions to a sum.
Non-negative: C(n + k − 1, k − 1)
Each >= 1: give everyone 1 first, then C(n − 1, k − 1)

"or" where the cases CAN overlap

Inclusion-exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|
"Divisible by 2 or 5" (10 is both), "distinct digits or even" (some are both).

Bounded constraint like "x1 <= 4" / "at most 2 Cokes"

Casework or inclusion-exclusion

Either sum over the allowed values (x1 = 0,1,2,3,4) or count everything and subtract the violations (x1 >= 5).

ℕ

Natural numbers

1, 2, 3, ...

ℤ

Integers

..., −2, −1, 0, 1, 2, ..

ℚ

Rational numbers

fractions

ℝ

Real numbers

all numbers on the number line

−2, 0.75, √2, π

ℂ

Complex numbers

3 + 2i, −i, 4