Fundamental Counting Rules
| Item | Description |
|---|
Multiplication Principle | If task A has m ways and task B has n ways, A-then-B has m*n ways |
Addition Principle | If tasks are mutually exclusive, total ways = sum of individual ways |
Factorial: n! = n*(n-1)*...*1 | Number of ways to arrange n distinct items — grows very fast |
0! = 1 | By convention — empty product; makes formulas work |
Permutation: P(n,k) = n!/(n-k)! | Ordered selection of k items from n (order matters) |
Combination: C(n,k) = n!/(k!(n-k)!) | Unordered selection of k items from n (order doesn't matter) |
Combinatorics Deep Dive
| Item | Description |
|---|
Permutations with Repetition: n^k | Each of k positions can be any of n items (PIN codes, passwords) |
Combinations with Repetition: C(n+k-1, k) | Stars and bars — selecting k items from n types, order irrelevant |
Permutations with Duplicates: n!/(n1!*n2!*...) | Arrange n items where some are identical — divide by duplicate counts |
Binomial Coefficient: C(n,k) = choose | Read as 'n choose k' — number of ways to pick k from n |
Pascal's Identity: C(n,k) = C(n-1,k-1) + C(n-1,k) | Recursive relationship — basis of Pascal's triangle |
Multinomial: n!/(k1!*k2!*...*km!) | Generalization: split n items into m groups of sizes k1,k2,... |
Binomial Theorem
| Item | Description |
|---|
(x + y)^n = Sum[C(n,k) * x^(n-k) * y^k] from k=0 to n | Expansion formula — coefficients are binomial coefficients |
Binomial Coefficient = coefficient of x^(n-k)*y^k | Appears in Pascal's triangle — row n, position k |
Application: (1+p)^n approx 1+np (small p) | Useful approximation for small probabilities |
Probability Rules
| Item | Description |
|---|
P(A or B) = P(A) + P(B) - P(A and B) | Addition rule — union; subtract intersection to avoid double-count |
P(A and B) = P(A) * P(B|A) | Multiplication rule — conditional probability chain |
P(B|A) = P(A and B) / P(A) | Conditional probability — probability of B given A occurred |
Mutually Exclusive: P(A and B) = 0 | Events cannot happen simultaneously; then P(A or B) = P(A) + P(B) |
Independent: P(A|B) = P(A) | Event A's probability unaffected by B occurring |
Pro Tip: The hardest part of combinatorics is choosing the right counting technique. Ask: Does order matter? (permutations) Or not? (combinations). Can items repeat?