Probability & Combinatorics

Cheatsheet Content

### Basic Probability - **Definition:** $P(A) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$ - **Range:** $0 \le P(A) \le 1$ - **Complement:** $P(A') = 1 - P(A)$ - **Mutually Exclusive Events:** $P(A \text{ or } B) = P(A) + P(B)$ if $A \cap B = \emptyset$ - **General Addition Rule:** $P(A \text{ or } B) = P(A) + P(B) - P(A \text{ and } B)$ - **Independent Events:** $P(A \text{ and } B) = P(A) \cdot P(B)$ if $A, B$ are independent - **Conditional Probability:** $P(A|B) = \frac{P(A \text{ and } B)}{P(B)}$ - **General Multiplication Rule:** $P(A \text{ and } B) = P(A|B) \cdot P(B)$ ### Factorials - **Definition:** $n! = n \times (n-1) \times \dots \times 2 \times 1$ - **Special Cases:** $0! = 1$, $1! = 1$ - **Example:** $4! = 4 \times 3 \times 2 \times 1 = 24$ ### Permutations - **Definition:** Order matters. Number of ways to arrange $k$ items from a set of $n$ distinct items. - **Formula (without repetition):** $P(n, k) = \frac{n!}{(n-k)!}$ - **Example:** Number of ways to arrange 2 letters from {A, B, C}: $P(3, 2) = \frac{3!}{(3-2)!} = \frac{3!}{1!} = 3 \times 2 = 6$ (AB, AC, BA, BC, CA, CB) - **Permutations with Repetition:** $n^k$ (e.g., lock combinations where digits can repeat) - **Permutations with Indistinguishable Items:** Number of distinct permutations of $n$ items where there are $n_1$ identical items of type 1, $n_2$ identical items of type 2, ..., $n_k$ identical items of type $k$: $\frac{n!}{n_1! n_2! \dots n_k!}$ - **Example:** Permutations of the letters in MISSISSIPPI: $\frac{11!}{1!4!4!2!} = 34,650$ ### Combinations - **Definition:** Order does NOT matter. Number of ways to choose $k$ items from a set of $n$ distinct items. - **Formula (without repetition):** $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ - **Example:** Number of ways to choose 2 letters from {A, B, C}: $C(3, 2) = \frac{3!}{2!(3-2)!} = \frac{3!}{2!1!} = \frac{6}{2 \times 1} = 3$ ({A, B}, {A, C}, {B, C}) - **Relationship with Permutations:** $C(n, k) = \frac{P(n, k)}{k!}$ - **Combinations with Repetition (Stars and Bars):** Number of ways to choose $k$ items from $n$ types with repetition allowed. $C(n+k-1, k) = \binom{n+k-1}{k}$ - **Example:** Choosing 3 scoops of ice cream from 5 flavors (repetition allowed): $C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!4!} = \frac{5040}{6 \times 24} = 35$ ### Binomial Theorem - **Formula:** $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$ - **Binomial Coefficients:** $\binom{n}{k}$ are the coefficients in the expansion. - **Properties:** - $\binom{n}{k} = \binom{n}{n-k}$ - $\binom{n}{0} = 1$, $\binom{n}{n} = 1$ - $\binom{n}{1} = n$ ### Bayes' Theorem - **Formula:** $P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$ - **Extended Form:** $P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B|A) \cdot P(A) + P(B|A') \cdot P(A')}$ - **Use:** Calculating conditional probability when $P(B|A)$ is known.