Permutation and Combination: An Overview

Permutation and combination is a very important chapter of Mathematics. Permutation and combinations problems are used in arrangements or counting object types of problems. Permutation means arranging objects in a specific order, where order matters. On the other hand, the combination means selecting objects with no specific order. The permutation and combination formulae can be derived from their definitions. Students can use a permutation and combinations calculator to check if their calculation is right. We will also discuss “permutation and combination meaning”, “permutation and combinations examples”, “permutation and combination difference” and “permutation and combination in discrete mathematics”.

To learn more about permutation and combination, students can also check “permutation and combinations pdf”, “permutation and combinations formula sheet”, and “permutation and combination ncert pdf”.

What is factorial?

A factorial is the product of all positive integers up to a given number.

It is denoted by n!.

n!=n ×(n-1)×(n-2)×(n-3)×………×2 ×1

It is calculated as follows.

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

Note that:

1! = 1

0! = 1

What is the meaning of n!?

n! is read as “n factorial”. It represents the products all positive integers from 1 to n.

n! = n × (n -1) × (n - 2) × (n - 3) × . . . . . . . × 1

It is used in various mathematical and real-world contexts like:

• Permutations and combinations

• In calculations involving probability distributions.

• Algebra and calculus

• Computer science algorithms involving combinatorial logic.

What are the Fundamental Principles of Counting?

Counting principles are foundational rules used to count the number of ways certain arrangements can occur.

It has two types.

• Principle of Addition

• Principle of Multiplication

Principle of Addition(OR rule)

If there are two tasks and they cannot be performed simultaneously or together, the total number of ways to perform either task is the sum of the number of ways to perform each task individually.

Example:

If Task A can be done in 3 ways and Task B can be done in 4 ways, and they are mutually exclusive, then either task A or task B can be done in 3 + 4 = 7 ways

In theorem wise, we can write it like,

If two sets A and B have no elements in common, then n(A ∪ B) = n(A) + n(B)

Principle of Multiplication(AND rule)

If there are two tasks and both can be performed in sequence, the total number of ways to perform both tasks is the product of the number of ways to perform each task individually.

Example:

If Task A can be done in 3 ways and Task B can be done in 4 ways, then both Task A and Task B can be done in 3 × 4 = 12 ways.

In theorem wise, we can write it like,

If there are “a” ways to event A and “b” ways to do event B, then there is a × b ways to do event A and B together.

n(A) = a

n(B) = b

n(A and B) = a × b

What is Permutation?

Permutation refers to the different possible arrangements of a given number of items taken some or all at a time.

Simply it can be said that it is a way to order data in different ways, typically taken from a list.

Permutation can be denoted by many different notations.

Some of them are:

• $^n p_r$

• P(n, r)

• npr

• pn, r

What is the formula for Permutation?

The number of permutations of “n” objects taken “r” at a time is given by:

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

Where

n = number of items

r = the number of items to be arranged

Types of Permutations

There are different types of permutations.

• Permutation of n different objects (when repetition is not allowed)

• Repetition, where repetition is allowed

• Permutation when the objects are not distinct (Permutation of multisets)

Permutation of n different objects (when repetition is not allowed)

In this case, each object is used only once in the arrangement.

The formula to find the number of permutations of n distinct objects is given by:

p(n) = n!

Where n! (n factorial) is the product of all positive integers up to n

Permutation of n different objects, where repetition is allowed

When repetition is allowed, each object can be used more than once in the arrangement. The formula to find the number of permutations when repetition is allowed is given by:

p(n,r) = nr

Where n is the total number of objects to choose from

And r is the number of positions to be filled

Permutation when the objects are not distinct (Permutation of multisets)

When some objects are identical, the formula to find the number of distinct permutations is adjusted to account for the repetitions. The formula is given by:

p(n; n1, n2, n3,......., nk) = $\frac{n!}{n_1! × n_2! × n_3! ×.........×n_k!}$

Where n is the number of total objects, n1, n2, n3,......., nk are frequencies of different objects.

What is Circular Permutation

When n objects are to be arranged circularly, then the formula to find the number of distinct permutations is given by (n-1)!.

What is the Combination?

A combination is a selection of items from a larger pool, where the order of the items does not matter. In other words, it is a way of selecting items where the arrangement or sequence of the selection is not considered.

What is the formula for Combination?

When is the Combination to be used?

Combinations are used when the order of selection does not matter. Here are some examples of when combinations are appropriate:

1. Lottery Selection Method: In the Lottery selection method, we use the combination method. Order does not matter in selecting lotteries to choose prize winners.

2. Forming Committees: When forming a committee from a group of people, the order in which members are chosen does not matter.

3. Choosing Subsets: When choosing a subset of items from a larger set, where the order in which items are chosen is irrelevant.

4. Hand of Cards: When selecting a hand of cards from a deck, the order of the cards in the hand does not matter.

Relation between Permutation and Combination

Theorem 1: $^np_r=^nc_r × r!$

Corresponding to each combination of $^nc_r$ we have r! permutations because r objects in every combination can be rearranged in r! ways.

Proof:

We have to prove that $^np_r=^nc_r × r!$

Taking the left side of the equation:

$^np_r=\frac{n!}{(n-r)!}$

Taking the right side of the equation

$^nc_r × r! = \frac{n!}{(n-r!) r!} × r! = \frac{n!}{(n-r)!}=^np_r$

Hence, $^np_r=^nc_r × r!$ proved.

Theorem2: ${ }^n\mathrm{C}_r +{ }^n\mathrm{C}_{r-1} = { }^{n+1}\mathrm{C}_r$

Proof:

We have to prove that ${ }^n\mathrm{C}_r +{ }^n\mathrm{C}_{r-1} = { }^{n+1}\mathrm{C}_r$

Taking the left side of the equation, we get,

${ }^n\mathrm{C}_r +{ }^n\mathrm{C}_{r-1}$

= $\frac{n!}{r!(n-r)!}+\frac{n!}{(n-r+1)!(r-1)!}$

= $\frac{n!}{(n-r)!r(r-1)!}+\frac{n!}{(n-r+1)!(r-1)!}$

= $\frac{n!}{(r-1)!}[\frac{1}{(n-r)!r}+\frac{1}{(n-r+1)!}]$

= $\frac{n!}{(r-1)!}[\frac{1}{r(n-r)!}+\frac{1}{(n-r+1)(n-r)!}]$

= $\frac{n!}{(r-1)!(n-r)!}[\frac{1}{r}+\frac{1}{(n-r+1)}]$

= $\frac{n!}{(r-1)!(n-r)!}[\frac{n-r+1+r}{r(n-r+1)}]$

= $\frac{n!}{(r-1)!(n-r)!}[\frac{n+1}{r(n-r+1)}]$

= $\frac{(n+1)n!}{r(r-1)!(n-r+1)(n-r)!}$

= $\frac{(n+1)!}{r!(n-r+1)!}$

= ${ }^{n+1}\mathrm{C}_r$

Hence, proved.

What are the differences between Permutations and Combinations?

Important Points

Practice Questions

Q1. A bookstore has 5 different mystery novels, 3 different romance novels, and 2 different fantasy novels. How many ways can you choose three mystery novels, two romance novels, and one fantasy novel to create a set?

1. 40 ways

2. 50 ways

3. 60 ways

4. 70 ways

Answer:

For the mystery novels, you have 5 choices, and you want to choose 3.
${ }^5 \mathrm{C}_3=\frac{5!}{3!(5-3)!}$ = 10 ways

For the romance novels, you have 3 choices, and you want to choose 2.
${ }^3 \mathrm{C}_2=\frac{3!}{2!(3-2)!}$ = 3 ways

For the fantasy novels, you have 2 choices, and you want to choose 1.
${ }^2 \mathrm{C}_1=\frac{2!}{1!(2-1)!}$ = 2 ways

$\therefore$ Total combination = 10 × 3 × 2 = 60 ways

So, there are 60 different ways to choose three mystery novels, two romance novels, and one fantasy novel to create a set.

Hence, the correct answer is 60 ways.

Q2. You have a collection of 10 different candies. If you want to create a bag of 3 candies, how many different combinations of candies can you put in the bag?

1. 30 combinations

2. 120 combinations

3. 220 combinations

4. 720 combinations

Answer:

To find the number of different combinations of 3 candies you can put in the bag from a collection of 10 different candies, you can use combinations. Specifically, you want to calculate the number of ways to choose 3 candies out of 10.

${ }^{10} \mathrm{C}_3=\frac{10!}{3!(10-3)!}=120$

So, you can create 120 different combinations of candies in the bag.

Hence, the correct answer is 120 combinations.

Q3. In how many different ways can the letters of the word 'PHENOMENAL' be arranged so that the vowels always come together?

1. 30,240 ways

2. 80,640 ways

3. 120,960 ways

4. 161,280 ways

Answer:

To find the number of different ways the letters of the word 'PHENOMENAL' can be arranged so that the vowels always come together, treat the vowels (E, O, E, A) as a single entity, which we can call "V."

Now, you have the letters "V," P, H, N, M, N, and L. These can be arranged in 7! ways.
However, the letter 'N' is repeated twice, so we must divide by 2! to account for the overcounting:

$= \frac{7!}{2!}$
$=\frac{7 × 6 × 5 × 4 × 3 × 2 × 1 }{2}$
$= \frac{5040}{2}$
$= 2520$

But the vowels (2 Es, O and A) can be permuted themselves.

$= \frac{4!}{2!}=\frac{4×3×2×1}{2×1}=12$

$\therefore$ The total number of arrangements will be = 2,520 × 12 = 30,240

Hence, the correct answer is 30,240 ways.

Q4. How many four-digit numbers can be formed using the digits {1, 8, 7, 4, 0, 9}(repetition of digits is not allowed)?

1. 120 numbers

2. 720 numbers

3. 360 numbers

4. 300 numbers

Answer:

1. For the first digit (the thousands place), you have 5 choices (any of the digits except 0).
2. For the second digit (the hundreds place), you have 5 choices (since you can't repeat the digit used for the thousands place, and 0 is also an option).
3. For the third digit (the tens place), you have 4 choices (excluding the two digits already used).
4. For the fourth digit (the unit place), you have 3 choices.

To find the total number of four-digit numbers that don't start with 0, you multiply the number of choices for each place:

$\therefore$ Total numbers = 5 (choices for the thousands place) × 5 (choices for the hundreds place) × 4 (choices for the tens place) × 3 (choices for the units place) = 5 × 5 × 4 × 3 = 300

So, 300 different four-digit numbers are using the given digits without repetition and not starting with 0.

Hence, the correct answer is 300 numbers.

Q5. A person has 5 hats and 8 pairs of shoes. In how many different ways can they select one hat and one pair of shoes?

1. 13 ways

2. 40 ways

3. 48 ways

4. 20 ways

Answer:

A person has 5 hats and 8 pairs of shoes.
He can choose one hat in ${ }^5 \mathrm{C}_1$ ways.
He can choose one pair of shoes in ${ }^8 \mathrm{C}_1$ ways.
$\therefore$ Total different ways = ${ }^5 \mathrm{C}_1×{ }^8 \mathrm{C}_1=\frac{5×4×3×2×1}{4×3×2×1}×\frac{8×7×6×5×4×3×2×1}{7×6×5×4×3×2×1}=5×8=40$

Hence, the correct answer is 40 ways.

Q6. In a question paper, there are 5 multiple-choice questions (labelled A, B, C, D, E) from different topics, and 10 essay questions (labeled as 1, 2, 3, ….). If a student needs to answer 5 questions such that he/she answers at least three essay questions to answer, how many different combinations of questions can the student select?

1. 2502 combinations

2. 2420 combinations

3. 2572 combinations

4. 2205 combinations

Answer:

To find the number of different combinations of questions a student can select when they need to answer at least three essay questions, you'll need to consider the different cases and then add them up.

Case 1: Selecting 3 essay questions and 2 multiple-choice questions.

- Combinations for selecting 3 essay questions from 10: ${ }^{10} \mathrm{C}_3$ = 120
- Combinations for selecting 2 multiple-choice questions from 5: ${ }^5 \mathrm{C}_2$ = 10
- Total combinations for Case 1: 120 × 10 = 1,200

Case 2: Selecting 4 essay questions and 1 multiple-choice question.

- Combinations for selecting 4 essay questions from 10: ${ }^{10} \mathrm{C}_4$ = 210
- Combinations for selecting 1 multiple-choice question from 5: ${ }^{5} \mathrm{C}_1$ = 5
- Total combinations for Case 2: 210 × 5 = 1,050

Case 3: Selecting 5 essay questions.

- Combinations for selecting 5 essay questions from 10: ${ }^{10} \mathrm{C}_5$ = 252
- Total combinations for Case 3: 252

$\therefore$ Total combinations = Case 1 + Case 2 + Case 3 = 1,200 + 1,050 + 252 = 2,502

So, there are 2,502 different combinations of questions the student can select to answer at least three essay questions.

Hence, the correct answer is 2,502 combinations.

Q7. In how many ways can 3 students, 2 teachers, and 1 staff member be selected from a group consisting of 5 students, 4 teachers, and 3 staff members?

1. 180 ways

2. 45 ways

3. 30 ways

4. 60 ways

Answer:

- For students, there are 5 choices to select 3 students: ${ }^5 \mathrm{C}_3=\frac{5!}{3!(5-3)!}$ = 10 ways
- For teachers, there are 4 choices to select 2 teachers: ${ }^4\mathrm{C}_2=\frac{4!}{2!(4-2)!}$ = 6 ways
- For staff members, there are 3 choices to select 1 staff member: ${ }^3 \mathrm{C}_1=\frac{3!}{1!(3-1)!}$ = 3 ways

$\therefore$ Total combination = 10 × 6 × 3 = 180 ways

So, there are 180 different ways to select 3 students, 2 teachers, and 1 staff member from the given group.

Hence, the correct answer is 180 ways.