October 5, 2020

Chapters

## Combinatorics - Introduction

Combinatorics or combinatorial mathematics is a branch of mathematics that deals with counting things. The problems related to the combinatorics were initially studied by the mathematicians from India, Arabia, and Greece. Some of the prominent mathematicians who studied these problems are Blaise Pascal, Leonhard Euler, and Jacob Bernoulli. Although combinatorics are helpful in many other fields of mathematics, however the most prominent of them are coding, cryptography, graph theory, and probability.

We can say that the combinatorics is mathematics of arranging and counting elements of a set. We know that counting objects is straightforward, however, combinatorics are useful to count quantities or arrangements that are too complicated if they are counted in a traditional manner.

The uses of combinatorics are not limited to mathematics, but they are spread to other areas such as computer science too. The techniques of combinatorics are used to determine the number of operations required by the algorithms. In discrete probability, the combinatorics techniques are employed to enumerate the possible outcomes in a uniform probability experiment.

There are many concepts within the field of combinatorics. These concepts include factorials, binomial theorem, combinations, and permutations. In this resource, we will study the formulas related to combinatorics. So, let us start with the factorials first.

## Factorials

We know that the combinatorics tell us the number of ways in which something can happen. In other words, we can say that the combinatorics tell us the number of possibilities in which different events can happen. For example, consider the following scenario:

**In a room, there are five people and five chairs in a row. In how many different orders can people sit on these chairs?**

It is hard to tell the number of possibilities without a formula. Fortunately, in the combinatorics we have a factorial formula that can be used to list down the number of arrangements in which the people can sit on the chairs. This formula is given below:

Number of arrangements =n!

It is read as n factorial. Since, in the above example, it is mentioned that 5 people are in the room and we have 5 chairs, therefore we will find the number of arrangements like this:

Number of arrangements = 5!

Hence, there can be 120 different arrangements of 5 people siting on 5 different chairs in a room.

## Permutations

We use the permutations formula to calculate the number of arrangements when the order of arrangement is important. There are two types of permutations:

- When repetition is allowed
- When repetition is not allowed

### When repetition is allowed

Suppose if you are given a problem in which you have to choose 3 digits from a set of 6 digits (0,1,2,3,4,5) to make a number. You will use the following formula in this case to calculate the number of permutations:

Here, n is the number of elements in a set

m is the number of elements that we will select from the set

We have assumed that the repetition is allowed because you can choose one digit twice, for example, the numbers can be 100, 202, 203, etc.

Putting the values in the above formula will give us the following number of permutations:

Number of permutations =

=216

Hence, 216 different permutations are possible.

### When repetition is not allowed

The formula to calculate the permutations when repetition is not allowed is given below:

Here, n = total number of things to select from

r = number of objects we want to select

For example, consider the following scenario:

**In a pool, there are 10 balls. You are asked to choose 5 balls from a pool. In how many possible arrangements, can you pick up the pool balls?**

Since, after picking up one ball, we cannot pick that again, therefore in this case we will use the formula of calculating the number of permutations without repetition.

=

=

Hence, 30240 permutations are possible.

If the total number of objects and the number of objects we want to select are equal then we use the following formula:

## Circular permutations

Circular permutation is the number of arrangements around a fixed circle. It is also known as cyclic permutation.

There are two types of cyclic or circular permutations:

- When clockwise and anticlockwise orders are different
- When clockwise and anticlockwise orders are the same

The formula for cyclic permutations when clockwise and anticlockwise orders are different is given below:

The formula for cyclic permutations when clockwise and anticlockwise orders are the same is given below:

## Combinations

Unlike permutations, you don't care about the order of selection in the combinations. There are two types of combinations:

- Combinations without repetition
- Combinations with repetition

**Combination without repetition**

The formula for finding the number of combinations without repetitions is given below:

Here:

n = total number of items to choose from

r = number of items we want to select

Consider the following scenario:

**In a shop, there are 4 balls of your favorite colors. You have money to buy 2 of them only. How will you choose 2 of them?**

Well in this example, the order in which you want to select the balls is not important, hence it is a combination problem. After selecting one ball you cannot choose that again, so it is a combination problem without repetition. Substitute the values in the above formula to get the number of possible arrangement:

Hence, you can choose 2 balls in 6 ways.

### Combinations with repetition

The formula to calculate the number of possible arrangements when the repetition is allowed is given below:

Here:

n = number of objects to choose from

k = number of items we want to choose

Consider the following scenario:

**Suppose there are 4 different ice cream flavors. You can only have two scoops. How many variations are possible?**

Order is not important while choosing the type of flavor. Hence, it shows that it is a combination problem. You can have one flavor twice because you are allowed two scoops. This shows that it is a combination problem with repetition. Substitute the values in the above formula to get the number of variation:

Hence, 10 variations are possible.

## Summary of formulas

**Permutation when repetition is allowed:**

Here, n is the number of elements in a set

m is the number of elements that we will select from the set

**Permutation when repetition is not allowed:**

Here, n = total number of things to select from

r = number of objects we want to select

**Circular**** permutation when clockwise and anticlockwise orders are different:**

**Circular**** permutation when clockwise and anticlockwise orders are the same:**

**Combination without repetition:**

**Combination with repetition:**

Here:

n = number of objects to choose from

k = number of items we want to choose