Combinations and Permutations

---

Combinations and Permutations

---

Combinations and permutations are two fundamental concepts in combinatorics, dealing with the ways in which a set of objects can be arranged or selected. The key difference lies in whether the order of selection matters.

---

1. Permutations

A permutation refers to an arrangement of objects where the order of the objects matters. Essentially, it counts the number of ways to arrange $r$ objects from a set of $n$ distinct objects.

Formula for Permutations:

The number of ways to arrange $r$ objects from $n$ distinct objects is given by the permutation formula:

$$P(n, r) = \frac{n!}{(n - r)!}$$

Where:

• $P(n, r)$ is the number of permutations of $r$ objects chosen from $n$.
• $n!$ is the factorial of $n$, the total number of objects.
• $(n - r)!$ accounts for the number of arrangements of the remaining objects.

Example 1:

Suppose you have 5 distinct books and you want to arrange 3 of them on a shelf. The number of ways to do this is:

$$P(5, 3) = \frac{5!}{(5 - 3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2!}{2!} = 60$$

So, there are 60 ways to arrange 3 books out of 5.

Example 2:

You have 7 people, and you need to select and arrange 4 of them for a team photo. The number of ways to do this is:

$$P(7, 4) = \frac{7!}{(7 - 4)!} = \frac{7!}{3!} = \frac{7 \times 6 \times 5 \times 4 \times 3!}{3!} = 840$$

So, there are 840 ways to select and arrange 4 people from 7.

---

2. Combinations

A combination refers to a selection of objects where the order does not matter. Combinations are used when the arrangement of the selected items is irrelevant. It counts the number of ways to select $r$ objects from a set of $n$ distinct objects without regard to order.

Formula for Combinations:

The number of ways to select $r$ objects from a set of $n$ distinct objects is given by the combination formula:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!}$$

Where:

• $C(n, r)$ is the number of combinations of $r$ objects chosen from $n$.
• $r!$ accounts for the fact that the order doesn't matter by dividing out the permutations of the $r$ objects.

Example 1:

Suppose you have 5 distinct books and you want to select 3 books to read. The number of ways to do this is:

$$C(5, 3) = \frac{5!}{3!(5 - 3)!} = \frac{5 \times 4 \times 3!}{3! \times 2!} = 10$$

So, there are 10 ways to select 3 books out of 5, where the order of selection doesn’t matter.

Example 2:

You have 7 people, and you need to select 4 of them to form a committee. The number of ways to do this is:

$$C(7, 4) = \frac{7!}{4!(7 - 4)!} = \frac{7 \times 6 \times 5 \times 4!}{4! \times 3!} = 35$$

So, there are 35 ways to select 4 people from 7 without regard to the order in which they are selected.

---

3. Key Differences Between Permutations and Combinations

• Order Matters:

  • Permutations: The order of the selected objects matters. For example, arranging books on a shelf (where the position of each book matters) involves permutations.
  • Combinations: The order of the selected objects does not matter. For example, selecting books from a shelf to read (where the selection itself, not the order of selection, matters) involves combinations.

• Formulae:

  • Permutations: $P(n, r) = \frac{n!}{(n - r)!}$
  • Combinations: $C(n, r) = \frac{n!}{r!(n - r)!}$

---

4. Examples of Applications of Permutations and Combinations

Permutations in Real Life:

1. Arranging people in a line: If you have 10 people and you want to arrange 3 of them in a specific order (e.g., for a photo or seating arrangement), you would use permutations.
2. Assigning tasks: If you are assigning 3 tasks to 3 people out of 10 people, the order in which tasks are assigned matters, so you use permutations.

Combinations in Real Life:

1. Choosing a team: If you have 10 players and need to select 5 to form a team, the order of selection does not matter, so combinations are used.
2. Choosing a subset of books: If you have 10 books and need to choose 3 books to read, the order doesn’t matter, so you use combinations.

---

5. Multinomial Coefficients (Generalization of Combinations)

When you need to select items from more than two groups (i.e., if you have multiple categories), you use multinomial coefficients. A multinomial coefficient generalizes combinations to the case of selecting multiple subsets from a set of objects divided into categories.

For example, the number of ways to divide a set of $n$ objects into $k$ groups with sizes $n_1, n_2, \dots, n_k$ is given by:

$$\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \dots n_k!}$$

Example:

Suppose you have 10 objects, and you want to divide them into 3 groups: 3 objects in the first group, 4 objects in the second group, and 3 objects in the third group. The number of ways to do this is:

$$\binom{10}{3, 4, 3} = \frac{10!}{3!4!3!}$$

---

Summary:

• Permutations: Arrangements where order matters. The formula is $P(n, r) = \frac{n!}{(n - r)!}$.
• Combinations: Selections where order does not matter. The formula is $C(n, r) = \frac{n!}{r!(n - r)!}$.
• Key Difference: Permutations are used when order is important; combinations are used when order does not matter.
• Multinomial Coefficients: A generalization of combinations used when dealing with multiple groups.

These counting methods form the core of combinatorics and are essential tools in solving problems related to arrangements, selections, and probability.