Create a resume that lands you SDE interviews at MAANG

Speaker

Anubhav Sinha

SDE-2 @

12 Jun, 2024 @ 01:30 PM

Introduction

Suppose you have a dictionary of words made only from 5 letters, P, E, A, C, E. Now, you are asked to find the position of PEACE from the start from all the possible words formed using the given letters when placed in the dictionary. The naive method to do this task is to create all the possible words from these five letters then find the position of PEACE in that. But that’s not the best way to do that, especially when you have many letters.

That’s where we use permutation and combination- they help us efficiently calculate the selections and arrangements of objects in different scenarios. So, let's begin with a brief definition of permutations and combinations, then we will learn about them and the different special cases for them in detail-

Permutation

If we try to arrange a given number of objects considering their order in the arrangement, then these arrangements are called permutations. The basic formulae to calculate the total number of permutations formed by taking r objects at a time from n number of distinct objects are-n!/(n-r)! n>=r.

Example- let’s suppose we have three numbers 1, 2, 3, now let’s see how many total permutations can be formed by any two numbers from these numbers-

{1,2},{1,3},{2,1},{3,1},{3,2},{2,3}, So total numbers of permutations are 6, this can be cross-checked by the formulae given above- nPr= n!/(n-r)!, with n=3, r=2.

3!/(3-2)!=3!=3*2=6

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Combination

If we select a few objects from a given number of objects, these selections are called combinations. The basic formulae to calculate the total number of Combinations of r objects at a time from n number of distinct objects are- n!/(r!)(n-r)!, n>=r.

Example- Let's suppose we have three numbers 1, 2, 3, now let's see the number of total combinations that any two numbers can form-

{1,2},{1,3},{3,2}, So total numbers of permutations are 3, Let’s check if it is equal to the result obtained by the formulae given above- nCr= n!/(r!)(n-r)!, with n=3, r=2.

3!/(2!)(3-2)!=3!/2!=3

Let’s see some important concepts apart from the ones given above, which are commonly used for solving problems on Permutations and combinations-

Concepts on arrangements of objects

Product rule

According to this rule, if we have A different ways to do the first activity and B different ways to do the second activity. Then the total number of ways we can perform both the activities will be A*B.

Example- Let's suppose we have three Slots 1, 2, 3 such that slot one can have A or B in it, Slot 2 can have C or D, or slot three can have E or F. then the total ways in which we can fill all the three slots will be 2*2*2=8, as {A, C, E}, {A, C, F}, {A, D, E}, {A, D, F}, {B, C, E}, {B, C, F}, {B, D, E}, {B, D, F}.

Sample problem- The number of 4-digit numbers (without repetition of digits) can be formed using the digits 0,1,2,3,4,5,6?

Solution- We have a total of 7 options to start, but since the left-most digit can't be zero, we have six options for the first digit. As 0 can be used at the second digit, thus we have six options for it. Now five options for the third digit and four options for the fourth digit. Therefore total no. of numbers that can be formed will be - 6*6*5*4=720.

Permutations of repeated objects

Suppose we have n number of objects such that A1 objects are alike, A2 objects are alike, A3 objects are alike. Then the total number of ways to arrange r objects out of these n objects is n!/A1!*A2!*A3!.

Example- Let's suppose we have five objects AA, BBB, then the total numbers of arrangements will be-

n!/A1*A2*A3=5!/2!*3!=10

Sample problem- Find the number of 7-digit numbers that can be formed by using the digits 1,1,2,2,2,3,3?

Solution- We have to form 7-digit numbers from 2-1s, 3-2s, and 2-3s. Therefore we can use the above formulae.

The total number of 7- digit numbers = 7!/2!*3!*2!=7*6*5=210.

Concepts on the selection of objects

Complimentary selection

It states that the number of ways we can select r objects out of n distinct objects is the same as the number of ways in which we can select (n-r) objects out of n distinct objects. i.e., nCr = nC(n-r).

Example-Suppose we have five letters A, B, C, D, E, then the total ways we can select two letters are- 5!/2!*3!=10

And if we have to select (5-2=3) objects from the five objects, the total number of ways of selection will be 5!/3!2!=10.

We see from the above example that the number of ways we can select two letters out of 5 letters is equal to the number of ways we can select three out of 5 letters.

Sample problem- What is the difference between the number of ways we can select four balls from a bag containing seven balls of different colors and the number of ways to select three balls from another similar bag of 7 balls of different colors?

Solution- The number of ways we can select four balls is- 7C4,

The number of ways we can select four balls is- 7C3,

Now, we need to find 7C4-7C3,

It will be 0 as 7C4 = 7C(7-4)=7C3.

Total number of selections

The total number of ways in which we can perform the selection of zero or more objects from n distinct objects is 2^{n}.

As the total number of subsets of a set = 2^{no. Of objects in the set}

Example-

Suppose we have three numbers 1,2,3, then the total number of selection is equal to the total number of ways of selecting zero objects+total numbers of ways of selecting one objects+total number of ways of selecting two objects+total numbers of ways of selecting three objects= 3C0+3C1+3C2+3C3=2^{3} =8.

Sample problem- A kid has six different flavors of candy to choose from, and he can buy at most six candies. Also, he can choose not to buy any candy. Find the total number of different combinations of the candies he can buy?

Solution- As there are six flavors of candies, each candy will be either chosen or not chosen by the kid, so the number of ways he can select the candies will be 2*2*2*2*2*2=2^{6}.

Distribution of Identical objects

Suppose we have n alike objects, and we have to distribute them among r people when anyone can get any number of objects.

Then the total number of distributions will be (n+r-1)C(r-1).

Example- Suppose we have to distribute A, A, A into two slots, and each slot can have any number of A(s). then the total number of different combinations will be(3+2-1)C(2-1)

Sample problem- Suppose we have seven candies and three people, find the total number of ways we can distribute candies among them, given that they can get any number of candies.?

Solution- We can use the above formulae with n=7, r=3.

The number of ways we can distribute the candies= (7+3-1)C(3-1)=9C2=36.

Relation between Permutations and Combinations

We know that the total number of permutations formed by taking r objects at a time from n number of objects are-n!/(n-r)!, n>=r.

And, the total number of Combinations of r objects at a time from n number of objects are- n!/(r!)(n-r)!, n>=r.

From above, we can observe that that nPr=nCr*r!

In simpler words, the arrangement of r objects out of n objects(nPr) is the selection of r objects out of n objects(nCr), then arrangements of these r objects, which will be rPr=r!.

Now, we will learn about the circular arrangements- The important thing to notice here is that all positions are identical until we have a reference point in a circular arrangement. It is sometimes already given in the question, or when you place the first object, it becomes a reference point.

Circular arrangements

Let’s learn about some of the important results on circular arrangements of the objects-

Circular arrangement on distinct objects

The total number of ways we can place ‘n’ distinct objects on ‘n’ positions around a circle is (n-1)!

If you have only one object in the picture above, you can not differentiate its position without the reference point. But, once we have a reference point. For example, if A is a reference point, we have seven different positions for any object as each position will be unique to the reference point.

That’s why when there is no reference point, the total number of arrangements is (n-1)!. As the first object has only one option, then the next n-1 distinct objects have n-1 positions.

The above result also concludes that if we have a reference point, then the total number of arrangements will be (n)! as the first object will have to choose from ‘n’ different positions.

Circular arrangements without considering the direction

Let’s consider another situation where the direction doesn’t matter in the circular arrangement-

Suppose A is the reference point, then there will be four different positions {B, H},{C, G},{D, F},{E} rather than 7 in the case of clockwise and anti-clockwise being different.

Thus the total number of arrangements will get halved. i.e., the total number of ways we can place ‘n’ distinct objects on ‘n’ positions around a circle is (n-1)!/2, if both the clockwise and anti-clockwise directions are identical.

Sample problem- we have five pens of different colors and five pencils of different colors. Find the number of ways we can place them alternatively around a circle.

Solution: Let’s start with placing the pens. Since there isn’t a reference point, there will be 4!=24, the total number of ways to place them.

Now, we have five positions left for pencils, and since these positions are unique to the reference, thus the total number of ways we can place the pencils will be 5!=120.

Now, the total number of ways we can place both the pens and pencils alternatively can be easily found using the product rule-

The total number of ways we can place both the pens and pencils=total number of ways we can place the pencils*total number of ways we can place the pens.

The total number of ways we can place both the pens and pencils=24*120=2880.

Frequently Asked Questions-

What is the difference between a permutation and a combination? The permutation is the number of arrangements of certain things, whereas the combination refers to the number of ways of selection.

Where is the combination used? The combination is used when we select a group of objects without considering their order of arrangements.

Find the case with more unique selections- selecting any three balls from a bag of 5 different balls or selecting any three balls from another bag of 5 balls in which three balls are alike? The number of unique selections will be more for selecting three balls from a bag of 5 different balls than from a bag of 5 balls in which three are alike. Because while we can only make three unique selections from 3 identical balls, three distinct balls can be selected in 8 unique ways. Thus the second case will have more unique selections.

What is a reference point in cyclic arrangements? In cyclic arrangements, each position is alike without a reference point. That’s why we need a reference point while making the arrangements, which is generally the position of the first object so that we can refer to all the other positions uniquely relative to the reference point.

What is the difference between linear arrangements and cyclic arrangements of objects? In the linear arrangements, we have a starting point and endpoint. But, in the case of a cyclic arrangement, we have a reference position, and we identify all other positions uniquely by their distance and direction from the reference point.

Key Takeaways-

In this blog, we learned about permutations and combinations, with some examples. Then we learned about the most common concept around them, generally asked in aptitude exams viz. Product rule, permutations of repeated objects, complementary selection, the total number of selections, distribution of identical objects, and circular arrangements. We also saw an example and sample problem for each concept to understand these concepts better.

You can learn more about permutations and combinations from here and practice similar problems on the Coding Ninjas Studio.

Live masterclass

Create a resume that lands you SDE interviews at MAANG

by Anubhav Sinha, SDE2 @ Amazon

12 Jun, 2024

01:30 PM

AI applications to thrive as an SDE: Practical industry examples

by Pranav Malik, SDE2@Microsoft

14 Jun, 2024

01:30 PM

Projects ideas to get shortlisted for data roles at MAANG

by Muskan Rathore, Data Scientist @ Microsoft

13 Jun, 2024

01:30 PM

Create a resume that lands you SDE interviews at MAANG

by Anubhav Sinha, SDE2 @ Amazon

12 Jun, 2024

01:30 PM

AI applications to thrive as an SDE: Practical industry examples