Permutation and Combination

Introduction to combinatorics

The area of mathematics in which counting is the primary concern is known as combinatorics. This has many applications in computer science.

The counting capabilities and other abstractions of combinatorics are implemented in different algorithms to obtain results. It also studies certain properties of finite structures, like data structures in computer science. Primarily, all data structures are related to some abstractions of some finite set. We can apply different types of permutations to finite sets, and that study also plays an important role in combinatorics.

Difference between combination and permutation

Let’s look at an example. Take the word “forget.” If we look it up in a thesaurus, we find several other words close to its meaning.

They include “overlook,” “drop,” “neglect,” “omit,” “leave out,” and more. We can rearrange these groups of words in many ways where the order is not maintained. When we don’t care what order the words are in, we say it’s a combination of words.

However, when we apply the alphabetical order and rearrange the group of words again, it comes out like this: drop, leave out, neglect, omit, overlook, etc. When order matters in a combination, it’s called a permutation.

Think about a combination lock. We can choose any three numbers from 0 to 9. If the combination works in the order of 562, we can say that repetition is not allowed in this permutation. If it’s 223, we can say that repetition is allowed in this permutation.

In any permutation where repetition is allowed, the number of possibilities is nothing but a factorial of the number of things to be rearranged.

Consider any three items. How many ways can we rearrange them? We can figure that out as follows:

$$3!$$ ...