Combinatorics and Probability

TL;DR

Combinatorics is about counting possibilities, helping you figure out how many ways something can happen. Probability uses these counts to determine the likelihood of an event occurring. Mastering both helps you solve problems where you need to count arrangements or predict outcomes.

1. The Mental Model

Think of combinatorics as figuring out all the different ways you can arrange or select things. Probability then uses those counts to tell you how likely a specific arrangement or selection is. It's like counting all the possible outfits you can make, then calculating the chance of picking one specific outfit.

2. The Core Material

You'll often hear about permutations and combinations. The main difference is whether order matters.

Permutations: Order Matters

Photo by Brett Jordan on Pexels

A permutation is an arrangement of items where the order is important. For example, if you're arranging books on a shelf, "ABC" is different from "ACB."

The number of permutations of n distinct items taken r at a time is given by:
P(n, r) = n! / (n - r)!

Where n! (n factorial) means n × (n-1) × ... × 1. For example, 4! = 4 × 3 × 2 × 1 = 24.

• Example: How many ways can you arrange 3 distinct books on a shelf from a selection of 5?
  Here, n = 5, r = 3.
  P(5, 3) = 5! / (5 - 3)! = 5! / 2! = (5 × 4 × 3 × 2 × 1) / (2 × 1) = 120 / 2 = 60 ways.

Combinations: Order Doesn't Matter

Photo by Brett Jordan on Pexels

A combination is a selection of items where the order doesn't matter. If you're choosing 3 friends to go to the movies, picking John, Mary, then Sue is the same as picking Sue, John, then Mary.

The number of combinations of n distinct items taken r at a time is given by:
C(n, r) = n! / (r! * (n - r)!)

Notice it's just the permutation formula divided by r!, because each group of r items can be ordered in r! ways, and we don't care about those different orderings.

• Example: How many ways can you choose 3 friends from a group of 5?
  Here, n = 5, r = 3.
  C(5, 3) = 5! / (3! * (5 - 3)!) = 5! / (3! * 2!) = (5 × 4 × 3 × 2 × 1) / ((3 × 2 × 1) × (2 × 1)) = 120 / (6 × 2) = 120 / 12 = 10 ways.

Probability: Likelihood of an Event

Photo by DS stories on Pexels

Probability is the measure of the likelihood that an event will occur. It's usually expressed as a number between 0 (impossible) and 1 (certain).

P(Event) = (Number of favorable outcomes) / (Total number of possible outcomes)

You'll often use combinatorics to figure out both the "number of favorable outcomes" and the "total number of possible outcomes."

graph TD
    A["Problem Statement"] --> B{"Does Order Matter?"}
    B -- "Yes, Order Matters" --> C["Use Permutations"]
    C --> D["Calculate P(n, r)"]
    B -- "No, Order Doesn't Matter" --> E["Use Combinations"]
    E --> F["Calculate C(n, r)"]
    D --> G["Result: Count of ordered arrangements"]
    F --> H["Result: Count of unordered selections"]
    G --> I["Probability P(Event) = (Favorable) / (Total)"]
    H --> I
    I --> J["Final Probability"]

3. Worked Example

Let's say you have a bag with 4 red marbles and 3 blue marbles. You randomly draw 2 marbles without replacement. What's the probability that both marbles are red?

1. Total possible outcomes: You're choosing 2 marbles from a total of 7 marbles. Order doesn't matter for the selection.
   C(7, 2) = 7! / (2! * (7 - 2)!) = 7! / (2! * 5!) = (7 × 6) / (2 × 1) = 42 / 2 = 21 ways.

2. Favorable outcomes: You want to choose 2 red marbles from the 4 available red marbles. Order doesn't matter.
   C(4, 2) = 4! / (2! * (4 - 2)!) = 4! / (2! * 2!) = (4 × 3) / (2 × 1) = 12 / 2 = 6 ways.

3. Calculate probability:
   P(Both marbles are red) = (Number of ways to pick 2 red) / (Total ways to pick 2 marbles)
   P(Both marbles are red) = 6 / 21 = 2 / 7.

So, there's a 2/7 chance (approximately 28.6%) that both marbles you draw will be red.

4. Key Takeaways

• Combinatorics helps you count possibilities, while probability uses those counts to predict likelihoods.
• Permutations are for counting arrangements where the order of items is crucial.
• Combinations are for counting selections where the order of items doesn't matter.
• The factorial symbol n! means multiplying n by every positive integer less than it down to 1.
• Probability is always a fraction or decimal between 0 and 1 (or 0% and 100%).
• Identify if "order matters" early in the problem to choose the correct counting method.

Common Mistakes to Avoid:

• Confusing permutations and combinations – always ask yourself if order matters.
• Forgetting to simplify factorials or fractions.
• Incorrectly identifying n (total items) and r (items chosen) in formulas.
• Calculating only favorable outcomes and forgetting the total possible outcomes for probability.

5. Now Try It

You're at a pizza shop, and they offer 8 different toppings. You want to choose 3 unique toppings for your pizza. How many different combinations of 3 toppings can you create? Once you have that, if one of those combinations is "pepperoni, mushrooms, and olives," what's the probability you'll pick exactly that combination at random? Write down your steps and final answers. You should get a whole number for the combinations and a simple fraction for the probability.