Module Review: Combinatorics

Congratulations on completing the Combinatorics module! This foundational knowledge is crucial for calculating probabilities, analyzing algorithms, and understanding data distributions.

Key Takeaways

  • Counting is Fundamental: Probability is essentially Target Outcomes / Total Outcomes. You must master counting first.
  • Order Matters?:
  • Yes → Permutations: P(n, k) = n! / (n-k)!. (e.g., Passwords, Races).
  • No → Combinations: C(n, k) = n! / (k!(n-k)!). (e.g., Lotteries, Committees).
  • Factorials Grow Fast: 10! is already 3.6 million. Brute-force solutions involving permutations are rarely feasible for large n.
  • Binomial Coefficients: Pascal’s Triangle gives the coefficients for expanding (x+y)n. In ML, this relates to the dimensionality explosion in polynomial kernels.
  • Don’t Double Count: Use the Inclusion-Exclusion Principle to correctly calculate the size of combined sets by subtracting overlaps.

Interactive Flashcards

Permutation vs. Combination

What is the key difference?

(Click to flip)

Order

In Permutations, order matters (AB ≠ BA). In Combinations, order does not matter (AB = BA).

Formula for C(n, k)

How do you calculate "n choose k"?

n! / (k!(n-k)!)

It is the permutation count divided by k! to remove duplicate orderings.

Binomial Expansion

What determines the coefficients of (x+y)n?

Combinations C(n, k)

The coefficient for the term xn-kyk is C(n, k).

Inclusion-Exclusion

What is the formula for |A ∪ B|?

|A| + |B| - |A ∩ B|

Sum individual sizes and subtract the intersection to correct double counting.

Combinatorics Cheat Sheet

Concept Formula Key Insight
Multiplication Rule m × n If events are sequential/independent, multiply possibilities.
Factorial n! = n × (n-1) … × 1 Ways to arrange n distinct items.
Permutation P(n,k) = n! / (n-k)! Order matters. (Password)
Combination C(n,k) = n! / (k!(n-k)!) Order doesn’t matter. (Team selection)
Binomial Coeff nCk = C(n,k) Coefficients in (x+y)n expansion.
Total Subsets 2n Total possible subsets of a set with n elements.
Inclusion-Exclusion |A| + |B| - |A ∩ B| Subtract overlap to avoid double counting.

Glossary & Next Steps

Review specific definitions in the Probability Glossary.

In the next module, Distributions, we will apply these counting techniques to model random variables and calculate actual probabilities.