Permutations and Combinations in Discrete Mathematics

---

---

In Discrete Mathematics, we frequently use permutations and combinations to solve different types of problems with discrete elements. Permutations and Combinations help us in counting the number of ways in which we can arrange or choose things. They are important in various real-life scenarios such as seating arrangements, selection processes, and organizing objects.

In this chapter, we will understand with examples the basics of permutations and combinations. We will focus on explaining the concepts through examples to make the math more relatable.

Permutations: Arranging Objects in Order

The term permutation refers the different ways we can arrange a set of objects in a specific order. For example, if we have three letters, say A, B, and C, the possible permutations (or arrangements) are −

• ABC
• ACB
• BAC
• BCA
• CAB
• CBA

So we are looking at the order of objects. Every time the order changes, it counts as a different permutation. One of the key formulas to calculate permutations involves factorials.

Factorial and Permutations

The factorial of a number n, written as n!. This represents the product of all positive integers from 1 to n. For instance, 4! = 4 × 3 × 2 × 1 = 24. In terms of permutations, if we are arranging n distinct objects, there are n! ways to do so. Let us understand this with an example −

Example 1: How many ways can we arrange the letters A, B, C, D, E, F?

We have six letters, and we need to find how many different ways you can arrange them. Using the factorial formula, we have −

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

Thus, there are 720 different ways to arrange these six letters.

Permutations of k Objects Chosen from n Objects

Sometimes, we are not interested in arranging all the objects but only a subset. In such cases, we use the formula for permutations of k objects chosen from n objects −

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

Here, n is the total number of objects, and k is the number of objects we want to arrange.

Example 2: How many ways can we arrange 4 letters from A, B, C, D, E, F?

We need to select 4 letters from a set of 6, and then find how many ways we can arrange them. Using the permutation formula −

$$\mathrm{P(6,4) \:=\: \frac{6!}{(6\:-\:4)!}\:=\:\frac{6\:\times\:5\:\times\:4\:\times\:3\:\times\:2!}{2!}\:=\: 360}$$

Thus, there are 360 different ways to arrange 4 letters from this set of 6.

Combinations: Selecting Objects without Considering Order

After knowing the idea of permutation we must understand the idea of combinations. This is similar but has a certain difference with permutations. Unlike permutations, combinations are about choosing objects without caring about the order.

Combinations is a way of selecting things, not arranging them. For example, if we are picking two colors from red, blue, and green, the possible combinations are −

• Red, Blue
• Red, Green
• Blue, Green

Notice how we do not care whether red comes before blue or blue comes before red. It is the same combination either way.

The formula to calculate combinations of k objects chosen from n objects is −

$$\mathrm{C(n,k) \:=\: \frac{n!}{k!(n\:-\:k)!}}$$

Example: How many ways can you choose 3 letters from A, B, C, D, E, F?

Here, we want to select 3 letters from a set of 6, but the order does not matter. Using the combination formula −

$$\mathrm{C(6,3) \:=\:\frac{6!}{3!(6\:-\:3)!} \:=\: \frac{6 \:\times\: 5 \:\times\: 4 \:\times\: 3!}{3! \:\times\: 3!} \:=\: \frac{120}{3!} \:=\: 20}$$

So, there are 20 different ways to choose 3 letters from the set of 6.

Difference between Permutations and Combinations

It is important to know the key difference between permutations and combinations:

• Permutations is about the order of objects. For example, ABC and BCA are different permutations.
• Combinations do not care about the order. ABC and BCA are considered the same combination.

We can remember them through analogies. One helpful analogy to understand this is to think about a combination of flavors for ice cream. We are picking flavors (combinations), but we do not care what order they are scooped into the cone.

Applying Permutation and Combination in Real Life

Permutations and Combinations are not just abstract mathematical ideas; they have real world applications. Let us see some examples −

Example 1: Dinner Party Seating Arrangement

Consider we are hosting a dinner party with 10 guests but we have only 6 chairs.

We need to choose 6 guests from the group of 10. This is a combination problem since the order in which we pick the guests does not matter. Only who gets a seat.

To calculate the number of ways we can select 6 guests, we use the combination formula −

$$\mathrm{C(10,6) \:=\: \frac{10!}{6!(10\:-\:6)!} \:=\: 210}$$

Now, if we need to assign seats to those 6 guests, we turn it into a permutation problem. Because the seating order matters −

$$\mathrm{P(10,6) \:=\: \frac{10!}{(10\:-\:6)!} \:=\: 151200}$$

This shows how permutations and combinations can both be used in the same scenario. It is depending on whether order matters.

Example 2: Creating Passwords

Another practical application of permutations could be related to creating passwords. Suppose we need to create a password using 5 letters from the alphabet. There is no repetition of letters. The order of letters matters in this case because "ABCDE" is different from "BCDEA".

So, we are getting with permutations −

$$\mathrm{P(26,5) \:=\: \frac{26!}{(26\:-\:5)!} \:=\: 7893600}$$

There are 7,893,600 possible ways to create a 5-letter password using the 26 letters of the alphabet.

In advanced problems, we might need to combine the use of both permutations and combinations to solve a problem. For example, we could first use combinations to select a group of objects and then use permutations to arrange them.

Example 3: Group Selection and Arrangement

We are forming a team of 4 people from a pool of 12, and we need to assign specific roles to each person in the team. First, we select the 4 people (combinations), and then we assign roles (permutations).

• Choosing 4 people from 12: C(12, 4)
• Assigning roles: P(4, 4)

Thus, the total number of ways to select the team and assign roles is −

$$\mathrm{C(12, 4) \:\times\: P(4, 4) \:=\: 495 \:\times\: 24 \:=\: 11880}$$

Conclusion

In this chapter, we explained the fundamental concepts of permutations and combinations in discrete mathematics. With appropriate examples, we demonstrated how to calculate permutations when the order of objects matters and combinations when it does not.