
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
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.