Counting Principles: Permutations & Combinations

1. The Fundamental Counting Principles

At the heart of all counting problems are two simple but powerful ideas: the Product Rule and the Sum Rule.

The Product Rule (Multiplication Principle)

Imagine you are building a computer. You have 3 CPU choices, 4 RAM choices, and 2 hard drive choices. How many different computer configurations can you build? Since you must choose one of each, you multiply the options: $3\times 4\times 2=24$ possible configurations.

This is the Product Rule: If a procedure can be broken down into a sequence of independent tasks, the total number of ways to perform the procedure is the product of the number of ways to do each task.

The Sum Rule (Addition Principle)

Now, imagine you want to travel from City A to City B. You can take one of 3 different bus routes or one of 2 different train routes. Since you can only take a bus or a train (not both at the same time), your total number of travel options is the sum: $3+2=5$ options.

This is the Sum Rule: If you have to choose between one of $n_1$ ways to do a task or one of $n_2$ ways to do another, and the tasks are mutually exclusive (you can't do both), the total number of ways is the sum $n_1+n_2$.

To see these principles in action with more examples relevant to your GATE preparation, please watch the following video segment.

2. Permutations: When Order Matters

Now let's get more specific. A permutation is an arrangement of objects in a specific order. Think about the top three finishers in a race. Gold, Silver, Bronze is a different outcome from Bronze, Silver, Gold, even if it's the same three people. The order matters.

Factorials

To count arrangements, we use the factorial function, denoted by an exclamation mark !. For a positive integer $n$, $n!$ (read as "n factorial") is the product of all positive integers up to $n$.
$n!=n\times (n-1)\times (n-2)\times \cdots \times 2\times 1$
For example, $4!=4\times 3\times 2\times 1=24$. By definition, $0!=1$.

The number of ways to arrange $n$ distinct items is simply $n!$.

The Permutation Formula

What if we don't want to arrange all the items? What if we want to select and arrange only $r$ items from a total of $n$ items? This is denoted as $P(n,r)$ or $nPr$.

The formula for permutations is:
$P(n,r)=\frac{n!}{(n-r)!}$

Example: In a club of 10 members, how many ways can we select a President, Vice-President, and Treasurer?
Here, we are selecting 3 people out of 10, and the order matters (President $\ne$ VP).

• $n=10$ (total members)
• $r=3$ (positions to fill)
  $P(10,3)=\frac{10!}{(10-3)!}=\frac{10!}{7!}=\frac{10\times 9\times 8\times 7!}{7!}=10\times 9\times 8=720$
  There are 720 ways to choose the officers.

For a clear explanation and the formula, please consult this resource.

3. Combinations: When Order Doesn't Matter

A combination is a selection of items where the order does not matter. Think about forming a study group. A group with students A, B, and C is the exact same group as C, B, and A.

The formula for combinations, denoted $C(n,r)$ or $nCr$, is:
$C(n,r)=\frac{n!}{r!(n-r)!}$
Notice this is just the permutation formula divided by $r!$. We divide by $r!$ to eliminate the different arrangements of the $r$ chosen items, since we don't care about their order.

Example: From the same club of 10 members, how many ways can we form a committee of 3 people?
Here, we are selecting 3 people out of 10, but the order doesn't matter.

• $n=10$
• $r=3$
  $C(10,3)=\frac{10!}{3!(10-3)!}=\frac{10!}{3!7!}=\frac{10\times 9\times 8}{3\times 2\times 1}=10\times 3\times 4=120$
  There are 120 ways to form the committee. As expected, this is fewer than the 720 permutations.

To deepen your understanding, let's turn back to the GeeksforGeeks video, which explains the distinction with a GATE-oriented perspective.

4. The Pigeonhole Principle

Another fundamental counting idea is the Pigeonhole Principle. It states that if you have more "pigeons" than "pigeonholes," at least one pigeonhole must contain more than one pigeon.

While it sounds obvious, it's a powerful tool for proving existence.

• Example: In a class of 30 students, can you guarantee at least two students share a birthday month?
  • Pigeons = 30 students
  • Pigeonholes = 12 months
  • Since $30>12$, yes, at least one month must have more than one student's birthday.

The GFG video provides some excellent examples that are common in competitive exams like GATE.

5. Counting in Python with itertools

As you know, we always want to bridge theory with practice. Python's standard library has a fantastic module called itertools that handles permutations and combinations for us. This is great for quickly generating all possibilities to check your reasoning or solve a coding problem.

Here is a quick example demonstrating the difference:

import itertools

my_list = ['A', 'B', 'C']

# Permutations of length 2: Order matters ('A', 'B') is different from ('B', 'A')
perms = itertools.permutations(my_list, 2)
print("Permutations of length 2:")
for p in perms:
    print(p)
# Output includes ('A', 'B'), ('B', 'A'), ('A', 'C'), ('C', 'A'), etc.

print("-" * 20)

# Combinations of length 2: Order does not matter ('A', 'B') is the same as ('B', 'A')
combs = itertools.combinations(my_list, 2)
print("Combinations of length 2:")
for c in combs:
    print(c)
# Output includes ('A', 'B'), ('A', 'C'), ('B', 'C') but NOT the reverse pairs.

Conclusion

In this lesson, we laid the groundwork for our study of probability by learning how to count. You now have the essential tools to determine the number of possible outcomes in various scenarios.

Key Takeaways:

• Product Rule: Use when tasks are sequential (AND). Total ways = product of ways for each task.
• Sum Rule: Use when tasks are mutually exclusive choices (OR). Total ways = sum of ways for each task.
• Permutations: Arrangements where order matters. Use $P(n,r)=\frac{n!}{(n-r)!}$.
• Combinations: Selections where order does not matter. Use $C(n,r)=\frac{n!}{r!(n-r)!}$.
• Pigeonhole Principle: A simple but powerful rule for proving that at least one category must contain multiple items.

Preview of the Next Lesson:

Now that we can count the number of outcomes, we are ready to start assigning probabilities to them. In the next lesson, we will move from "how many?" to "how likely?". We will learn how to calculate probabilities using axioms, conditional probability, and the famous Bayes' theorem.