Chapter 6 Basics of Counting

product rule - example: a procedure can be broken down into two tasks. there are n1 ways to do the first task and n2 ways to do the second task. then there are n1n2 ways to do the entire procedure.

sum rule - example: a task can be done in one of n1 ways or one of n2 ways, where none of the ways overlap. so there are n1 + n2 ways to do the task.

subtraction rule - a task can be done in either n1 ways or n2 ways, with overlap. the total number of ways to do the task is n1 + n2 - nC. nC is the common ways between n1 and n2.

inclusion-exclusion principle - let A and A2 be sets. then the number of elements in their union is |A1 U A2| = |A1| + |A2| - |A1 N A2|

division rule - a task can be done in n ways, and for each way w, exactly d of the n ways correspond to the way w. then there are n/d ways to do the task.

tree - has a root, # of branches, and branches from branches.

leaf - a branch that terminates at an endpoint with no next branch.

tree diagrams - a branch represents a possible choice, leaf represents possible outcome