> See also: > - [[Inclusion-Exclusion Principle]] > - [[Permut stributing Objects]]" --- > See also: > - [[Inclusion-Exclusion]] > - [[Permutations]] > - [[Distributing Objects]] # Combinatorics **Combinatorics** is the mathematics of *counting and arranging* (particularly counting quantities that are much too large to be counted the conventional way). - A **combinatorial proof** of an identity is a proof that uses counting arguments to prove that both sides of the identity count the same objects but in different ways or a proof that is based on showing - On the other hand, an **algebraic proof** will ... ## Basic Operations of Counting ### The Addition Rule > [!note]- **The Addition Rule (OR)** > If a task can be done *either* in one of $n_1$ *or* in one of $n_2$ ways, where none of the set $n_1$ is the same as any of the set of $n_2$, then: > > **There are** $n_1 + n_2$ **ways to do the task.** If two events are “disjoint”, then they can be added together using the addition rule without causing any overlap/overcounting issues ### The Subtraction Rule The subtraction rule is simply the [[Inclusion-Exclusion Principle]] principle applied to counting. A common technique when solving combination problems is to *over count* the amount of possibilities and then *subtract out* the excess choices to find the true answer. > [!note]- The Subtraction Rule > If a task can be done in either $n_1$ ways or $n_2$ ways, then the number of ways to do the task is $n_1 + n_2$, minus the number of ways to do the task that are common in the two different ways. ### The Product Rule > [!note]- **The Product Rule** (AND) > Suppose that a procedure can be broken down into a sequence of two tasks. > > If there are $n_1$ ways to do the first task and *for each of these ways of doing the first task* there are $n_2$ ways to do the second task, then: > > There are $n_1 \times n_2$ ways to do the procedure. A common mistake made when solving combination problems is confusing when to use the sum and product rules. Ex: - If each step taken *influences the amount of possible choices in future steps* (Ex: a sequence of unique digits) ### The Division Rule While the subtraction rule often serves to correct for overlap caused by the addition rule, the division rule can serve a similar purpose and *correct for overlap caused by the product rule*. > [!note]- **The Division Rule** > There are $n/d$ ways to do a task if it can be done using a procedure that can be carried out in $n$ ways, and for every way $w$, exactly $d$ of the $n$ ways correspond to way $w$. ## Compensating for Disjoint (+) Complement (-) Independent (\*) Overcounting (/)