Permutations, Combinations, and the Counting Principle

Hello! Welcome to the first lesson in our new module, Combinatorics and Probability. We're making a significant shift from the geometric world of coordinates and shapes to the logical realm of counting, arrangements, and selections.

As we discussed at the end of our last lesson, today we'll tackle the absolute foundation of this topic. Our goal is to distinguish between permutation and combination scenarios and apply the fundamental counting principle. Mastering this skill is about developing a systematic way to think about problems, which is crucial for the CAT. Let's begin.

1. The Foundation: The Fundamental Counting Principle (FCP)

At its heart, combinatorics is just a structured way of counting possibilities. The most basic tool we have is the Fundamental Counting Principle (FCP).

The principle states that if an event can occur in $m$ ways, and a second, independent event can occur in $n$ ways, then the total number of ways that both events can occur in sequence is $m \times n$ .

Imagine ordering a meal. If you have 3 choices for a main dish, 3 for a side, and 2 for a drink, how many different meal combinations are possible? The FCP tells us to simply multiply the number of choices at each stage.

Fundamental Counting Principle Tree Diagram — This tree diagram visually demonstrates the Fundamental Counting Principle. Starting with 3 main dishes, each branches into 3 side dishes, and each of those branches into 2 drinks, resulting in $3 \times 3 \times 2 = 18$ unique meal possibilities.

This simple idea of multiplying choices is the engine behind almost everything else we will do in this topic. To see it applied in a few more contexts, please read the following section from a helpful text.

Chapter 1 – Counting Methods

The document 'Chapter 1 – Counting Methods' provides a clear introduction to the FCP with several good examples.

Read Section 1.2, 'Fundamental Counting Principle'. Focus on how the principle is applied to the breakfast order, phone number, and job-ordering examples. Notice how each problem is broken down into a series of 'steps' or 'slots', with the number of choices for each being multiplied.

As you saw, the FCP can be used to solve problems like:

Finding the number of possible phone numbers with certain restrictions.
Determining the number of ways a series of tasks can be performed.

Test your understanding!

A 4-digit ATM PIN is to be created using the digits 0 through 9.

How many different PINs are possible if digits can be repeated?
How many different PINs are possible if digits cannot be repeated?

Show answer

Think of this as filling four slots: _ _ _ _

Digits can be repeated: Each of the four slots has 10 possible choices (0-9).
Total PINs = $10 \times 10 \times 10 \times 10 = 10, 000$ .
Digits cannot be repeated:
- The first slot has 10 choices.
- The second has 9 choices left.
- The third has 8 choices left.
- The fourth has 7 choices left.
  Total PINs = $10 \times 9 \times 8 \times 7 = 5, 040$ .

This is a direct application of the FCP.

2. The Crucial Distinction: Permutations vs. Combinations

Now we move to the most important concept in this lesson: understanding the difference between a permutation and a combination. Almost every basic counting problem will require you to make this distinction correctly.

Permutation: An arrangement of items where the order matters. Think of it as assigning specific roles or positions.
Combination: A selection of items where the order does not matter. Think of it as forming a group.

Permutations vs. Combinations Visual Explanation — This image clearly shows the difference. When choosing 2 letters from {A, B, C, D}, there are 6 combinations (unordered groups), but 12 permutations (ordered arrangements), because for permutations, AB is different from BA.

The key question you must always ask when facing a word problem is: "Does the order in which I choose the items change the outcome?"

If YES, it's a Permutation.
If NO, it's a Combination.

Let's solidify this with some clear, practical examples from an excellent guide.

Permutation and combination :An easy method . Must read

The article 'Permutation and combination :An easy method' uses simple, memorable examples to make the distinction very clear.

Read the first two parts of the article, focusing on the 'Ugliest Dog competition' example for permutations and the 'Brandon and his dogs' example for combinations. Pay close attention to why one is a permutation (the rank of the ribbon matters) and the other is a combination (the group of dogs is the same regardless of who was called first).

3. Calculating Permutations and Combinations

Once you've identified the type of problem, the next step is calculation. While formulas exist, a more intuitive approach for exams is the "slots" method, which builds directly on the FCP.

Calculating Permutations (Order Matters)

A permutation is a direct application of the FCP where the number of choices decreases with each selection.

Example: From a group of 8 people, we need to elect a President, a Vice-President, and a Treasurer. How many ways can this be done?

This is a permutation because the positions are different. (Person A as President, B as VP is different from B as President, A as VP).
We have 3 slots to fill: President, VP, Treasurer.
- For President, we have 8 choices.
- For VP, we have 7 choices left.
- For Treasurer, we have 6 choices left.
Total ways = $8 \times 7 \times 6 = 336$ .

This is written as $^{8} P_{3}$ . The formula is $^{n} P_{r} = \frac{n !}{( n - r )!}$ , but the slot method is often faster.

Calculating Combinations (Order Doesn't Matter)

For combinations, we start the same way as permutations, but then we must divide out the duplicates created by ordering.

Example: From a group of 8 people, we need to choose a committee of 3. How many ways can this be done?

This is a combination because it's just a group. A committee of {A, B, C} is the same as {C, B, A}.
Step 1: Calculate the permutations first.
- $8 \times 7 \times 6 = 336$ .
Step 2: Divide by the number of ways the chosen group can be arranged.
- A group of 3 people can be arranged in $3 \times 2 \times 1 = 3! = 6$ ways.
- Total ways = $\frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$ .

This is written as $^{8} C_{3}$ . The formula is $^{n} C_{r} = \frac{n !}{r ! ( n - r )!}$ .

The following resource explains this "easy method" very well.

Permutation and combination :An easy method . Must read

Let's return to the 'easy method' article to see how to apply the slot method for both permutations and combinations.

Read the rest of the article ('The Method' and the fraternity examples). Focus on how the calculation for combinations includes the extra division step on the bottom, which is what removes the duplicate arrangements.

For a more formal look at the formulas and definitions, you can quickly skim the corresponding sections in the PDF we looked at earlier (LINK, Sections 1.3 and 1.4), but for speed during the CAT, the "slots" method is highly effective.

Test your understanding!

There are 10 players on a team.

In how many ways can the coach pick a captain and a vice-captain?
In how many ways can the coach pick a group of 2 players to go to a press conference?

Show answer

Captain and Vice-Captain: The order matters (Player A as Captain, B as VC is different from B as Captain, A as VC). This is a permutation.
- Ways = $10 \times 9 = 90$ .
Group of 2 players: The order doesn't matter (A and B going is the same as B and A going). This is a combination.
- Ways = $\frac{10 \times 9}{2 \times 1} = 45$ .

Conclusion

Today, we've laid the critical groundwork for all of combinatorics. The ability to correctly identify a problem as a permutation or a combination is more than half the battle won.

Key Takeaways:

Fundamental Counting Principle (FCP): If you have a sequence of choices, the total number of outcomes is the product of the number of options at each step.
The Golden Question: Always ask yourself, "Does the order of selection matter?"
Permutations (Arrangements): Order matters. Use the slot method: $n \times (n - 1) \times \dots$
Combinations (Selections): Order does not matter. Use the slot method and divide by the factorial of the number of items selected: $\frac{n \times ( n - 1 ) \times \dots}{r \times ( r - 1 ) \times \dots}$

Preview of the Next Lesson:
Now that we have the basic tools for counting arrangements and selections, we'll move on to more complex scenarios. In our next lesson, we will learn how to solve arrangement problems with and without restrictions, such as arranging items where some must always be together or must never be next to each other.

Recommended resources