Introduction to Counting Principles

TL;DR

Counting principles help you figure out the total number of ways something can happen without listing every single possibility. You'll learn the Fundamental Counting Principle for sequential choices and how permutations and combinations handle order and repetition. Mastering these saves you tons of time and helps solve probability problems.

1. The Mental Model

Imagine you're making choices, one after another. Counting principles are like a mental shortcut to figure out all the unique "paths" you could take through those choices, saving you from drawing massive diagrams or lists.

2. The Core Material

Counting principles are all about determining the number of possible outcomes or arrangements. They're super useful in probability, data science, and many other areas.

The Fundamental Counting Principle (FCP)

Photo by Black ice on Pexels

This is the bedrock of counting. If you have several independent choices to make, the total number of ways to make all those choices is simply the product of the number of options for each choice.

Let's say you're getting dressed:
* You have 3 shirts.
* You have 2 pairs of trousers.
* You have 4 pairs of shoes.

To find the total number of different outfits you can make, you multiply the number of options for each choice:
Total Outfits = (Number of Shirts) × (Number of Trousers) × (Number of Shoes)
Total Outfits = 3 × 2 × 4 = 24 different outfits.

Permutations

Permutations are about counting arrangements where order matters. Think of it like arranging items in a line – if you swap two items, it's considered a new arrangement.

There are two main types:

• Permutations of all items: If you have 'n' distinct items and want to arrange all of them, the number of permutations is 'n!' (n factorial).

  • n! means n × (n-1) × (n-2) × ... × 1. For example, 4! = 4 × 3 × 2 × 1 = 24.
  • If you have 3 distinct books (A, B, C) and want to arrange all of them on a shelf, there are 3! = 3 × 2 × 1 = 6 ways (ABC, ACB, BAC, BCA, CAB, CBA).

• Permutations of 'k' items from 'n' items: If you have 'n' distinct items and want to choose and arrange 'k' of them (where k ≤ n), the formula is:
  P(n, k) = n! / (n - k)!

  • Example: You have 5 people, and you want to choose 3 of them to stand in a specific order for a photo.
    P(5, 3) = 5! / (5 - 3)! = 5! / 2! = (5 × 4 × 3 × 2 × 1) / (2 × 1) = 120 / 2 = 60 ways.

Combinations

Combinations are about counting selections where order does NOT matter. Think of it like picking items for a group – if you pick Alice then Bob, it's the same group as picking Bob then Alice.

The formula for choosing 'k' items from 'n' distinct items (where k ≤ n) when order doesn't matter is:
C(n, k) = n! / (k! * (n - k)!)
This is often read as "n choose k".

• Example: You have 5 people, and you want to choose 3 of them to form a committee. The order you pick them in doesn't change who's on the committee.
  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.

Notice that combinations always give you a smaller or equal number of ways than permutations for the same n and k, because they discount arrangements that are just different orderings of the same set.

Here's a quick way to think about when to use which:

graph TD
    A["Does order matter?"] -->|Yes| B["Is repetition allowed?"]
    A -->|No| C["Combinations (Order doesn't matter)"]

    B -->|Yes| D["Power (n^k) or similar"]
    B -->|No| E["Permutations (Order matters, no repetition)"]

    C --> F["C(n, k) = n! / (k!(n-k)! )"]
    E --> G["P(n, k) = n! / (n-k)! "]
    E --> H["n! (if k=n)"]

Repetition

Sometimes, items can be repeated.
* With the Fundamental Counting Principle, this is naturally handled. If you can use a digit multiple times for a lock code, each slot just has the full number of options.
* Permutations with repetition: If you have 'n' items where some are identical (e.g., the letters in the word MISSISSIPPI), the formula is n! / (n1! * n2! * ... * nk!), where n1, n2, ... nk are the counts of each repeated item.
* MISSISSIPPI has 11 letters: 1 M, 4 I's, 4 S's, 2 P's.
* Arrangements = 11! / (1! * 4! * 4! * 2!)

3. Worked Example

Let's say you're a coach for a 100-meter race, and you have 8 runners.

Scenario 1: Gold, Silver, and Bronze Medals
How many different ways can the gold, silver, and bronze medals be awarded among the 8 runners?

• Does order matter? Yes, finishing first is different from finishing second.
• Are the runners distinct? Yes.
• Are we using all items? No, only 3 out of 8.

This is a permutation problem: P(n, k) where n=8 and k=3.
P(8, 3) = 8! / (8 - 3)! = 8! / 5! = (8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) / (5 × 4 × 3 × 2 × 1)
P(8, 3) = 8 × 7 × 6 = 336

There are 336 different ways to award the gold, silver, and bronze medals.

Scenario 2: Choosing a Team of 3
You need to select 3 runners out of the 8 to represent the school in a relay race. The order you pick them in doesn't matter; it's just about who's in the team.

• Does order matter? No.
• Are the runners distinct? Yes.
• Are we using all items? No, only 3 out of 8.

This is a combination problem: C(n, k) where n=8 and k=3.
C(8, 3) = 8! / (3! * (8 - 3)!) = 8! / (3! * 5!)
C(8, 3) = (8 × 7 × 6 × 5!) / ((3 × 2 × 1) × 5!)
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 336 / 6 = 56

There are 56 different ways to choose a team of 3 runners.

4. Key Takeaways

• The Fundamental Counting Principle: Multiply the number of options for each independent choice to get the total number of outcomes.
• Permutations: Use when the order of arrangement matters (e.g., passwords, race finishes, specific positions).
• Combinations: Use when the order of selection doesn't matter (e.g., committees, lottery picks, choosing a group).
• Factorials (n!) are shorthand for multiplying an integer by all positive integers less than it down to 1.
• Combinations always result in fewer ways than permutations for the same n and k, because combinations don't count different orderings of the same set as unique.
• Repetition needs special consideration; the methods change depending on whether items can be reused or if identical items exist.

Common Mistakes to Avoid:

Photo by KATRIN BOLOVTSOVA on Pexels

• Mixing up permutations and combinations: Always ask yourself, "Does the order of selection or arrangement make a difference?"
• Forgetting the "no repetition" vs. "with repetition" distinction: Most formulas assume no repetition unless stated otherwise.
• Incorrectly calculating factorials: 0! is defined as 1, which is important in the formulas.
• Not simplifying calculations: For example, 8!/5! is 8*7*6, not 8*7*6*5*4*3*2*1 / 5*4*3*2*1.
• Jumping straight to a formula: Always understand the underlying problem first, then choose the appropriate counting method.

5. Now Try It

You're at a sandwich shop. There are 5 types of bread, 8 types of fillings, and 3 types of cheese. You must choose one of each. Then, you also need to pick 2 different toppings out of 6 available toppings (e.g., lettuce, tomato, onion, etc.).

1. How many different sandwich combinations (bread, filling, cheese) can you make?
2. After picking your sandwich, how many ways can you choose 2 different toppings from the 6 available? (The order you put the toppings on doesn't matter).
3. What's the total number of unique sandwich-and-topping combinations you can create?

Success looks like: You've correctly identified when to use the FCP, and when to use a combination, and you've calculated the final total.