Theory of Counting

What is the Product Rule?

Used to count the total number of ways to perform a sequence of independent tasks, wherein each task can be completed in multiple ways. If you have Ti tasks, each of which can be completed in ni ways, then there are n1 x n2 x n3 etc. ways to perform the tasks.
TLDR: You multiply for independent tasks.

What is the Sum Rule?

Used to count the total number of ways to perform one of several mutually exclusive tasks. If you have Ti tasks, each of which can be completed in ni ways, then there are n1 + n2 + n3 etc. ways to complete task Ti.
TLDR: You add for mutually exclusive tasks.

What is the Inclusion-Exclusion Principle?

Used to count the total number of elements in the union of multiple sets.
        

∣A∪B∣ = ∣A∣ + ∣B∣ - ∣A∩B∣

What is the Permutation Principle?

Used to count the arrangements of either distinguishable or indistinguishable elements.

What is the Permutation Principle for Distinguishable Elements?

P(n,r)= n!/(n-r)!
An r-permutation is an ordered arrangement of r elements. We use the factorial ‘!’ to denote the decreasing number of ways things can be arranged, having already arranged some.

What is the Permutation Principle for Indistinguishable Elements?

n!/(n1! × n2! × … × nk!)
For elements that can only be categorized, we use the number of elements overall OVER n1, the number in category one, TIMES n2, the number in category 2.

What is the Combination Principle?

Used to count the number of ways to select a subset of items from a larger set. Combinations don’t consider unique arrangements.
C(n,r) = (n/r) = n!/((n-r)! ×r!)

What are the probability axioms? (6)

1. The probability of an event occurring is the event OVER the total events that could occur.

2. The probability of an event is always expressible by a number between 0 and 1.

3. Disjoint events are events whose probabilities of occurring don’t effect each other.

4. The Complement Rule says that you can find the probability that an event does not happen by subtracting the probability that it does happen from 1.

5. The Impossible Rule states that the probability of an impossible event is zero.

6. The General Addition Rule states P(E1∪E2)=P(E1)+P(E2)-P(E1∩E2), which is the exact same as the Inclusion-Exclusion Principle.

7. If E1⊆E2 then P(E1) ≤P(E2) - this means that if E1 is a subset of E2, then the probability of E1 occurring is less than or equal to the probability of E2 occurring. This is because if everything in E1 is also in E2, then the chance of E1 happening can’t be more than the chance of E2 happening.