Permutation and Combination Solution Set 1

permutation and combination exercise solution set 1

This is the 1st solution set to the 10 practice problem exercise in the tutorial on Permutation and Combination. For extracting maximum benefits from this solution set, students should first go through the tutorial, do the exercise and then refer to this solution set.

First Solution set- 10 problems on Permutation and Combination - time 30 mins

Problem 1.

How many 5 letter words (may not be meaningful) out of the first eight letters of the English alphabet can be formed with the vowels always included?

  1. 1600
  2. 900
  3. 4800
  4. 2400

Solution:

The vowels among the first eight letters of the alphabet are only two: 'a' and 'e'. Rest six letters are consonants. In each of the 5 letter word that we have to form, these two vowels must be included. This is the primary condition of the problem.

Let us deal with this condition first.

Assigning two letters [a, e] to any two positions of the 5 letter positions of a target word

We would first find out in how many possible ways we can place the two vowels in any two of the 5 positions of the target word fulfilling the first condition of including the two vowels in every target word.

Usually in permutation problems, the number of vacant slots or positions are equal to or smaller than the number of distinct objects that would fill up the slots. All 3 letter permutations out of 5 letter set is a ready example. The 3 positions of the 3 letter permutations are the empty slots or positions where systematically the 5 letters are placed filling up the first slot in 5 ways, second slot in remaining 4 ways and the third slot in remaining 3 ways. We obtain the total number of permutations out of this systematic methodical approach as $5\times{4}\times{3}$.

But in this case of our problem, the situation is just the opposite. Here the vacant slots are 5 and the objects or letters that are to be placed are 2.

Rich concept: Equivalence of Object to Permutation place assignment: Permutation assignment equivalence principle

When we assign an object out of a set of objects to an ordered and uniquely identified position of the permutation (for example, assign letter $a$ out of letters $a$ and $e$ to position 1 of a 5 letter permutation), the unique place is also assigned to the distinct object. In other words, when we start to permute, the assignments of objects to permutation places are bothway and equivalent.

permutation assignment equivalence

In the figure, positions 1 and 5 of the 5 letter word have been assigned to the two vowels $a$ and $e$. This is expressed as,

Assignment = [(1, a), (5, e)] $\equiv$ [(a, 1), (e, 5)].

Assigning position 1 to letter $a$ is same and equivalent to assigning letter $a$ to position 1.

Carrying on with assigning positions to the two vowels then, the first vowel can be assigned in 5 ways and for each of these, the second vowel can be assigned in remaining 4 ways, that is, a total of $^5P_2 = 5\times{4} = 20$ ways.

Because of assignment equivalence, this 20 ways is nothing but all the ways we can place the letters $a$ and $e$ in the 5 vacant positions.

Applying this permutation assignment equivalence property we restated our problem fragment as,

To find in how many ways the five uniquely identified positions of a five letter target word can be assigned to the two vowels $a$ and $e$.

This is simply the permutations of 2 out of 5, that is 20, and then we reverted back to the actual state using assignment equivalence, "all possible ways $a$ and $e$ can be placed to any two positions of 5 letter target word is 20".

Filling up the rest of the three empty positions

In each of these 20 arrangements in which two of the 5 positions are filled up by the two vowels, we have 3 positions empty and rest 6 letters ready to be assigned. The number of ways we can do this is, $^6P_3 = 6\times{5}\times{4} = 120$.

So for 20 arrangements we would have all possible target words in which the two vowels are always included as, $20\times{120} = 2400$.

Answer: d: 2400

Concepts used:

Rich concept of Permutation assignment equivalence -- enumeration of assigning 5 positions to two vowels -- permutation concept to rest three empty positions.

Problem 2.

How many 3 digit even numbers greater than 500 can be formed out of the digits 6, 0, 3, 5 and 4?

  1. 9
  2. 12
  3. 15
  4. 18

Solution:

First conclusion:

For the target numbers to be greater than 500, the 3rd digit from right cannot be 0, 3 or 4, it has to be only 5 and 6. This our first conclusion.

Second conclusion:

Again for the target numbers to be even, the 1st digit from right must be 0, 4 or 6, it can't be 3 or 5.

Third conclusion:

As 6 can take up 3rd or 1st position, because of overlapping of occupancy restriction, it would be methodically more reliable and conceptually easier, if we take up the two cases where 5 and 6 occupies the 3rd place separately, thereby breaking up the problem into two subproblems.

First stage of Enumeration of permutations:

Considering 5 taking up 3rd position, there are two positions to be filled up and 4 digits left. The number of possible permutations would have been, $^4P_2 = 4\times{3} = 12$. But as 3 can't take up the 1st position, to follow a conceptually clear and reliable path, out of the two positions 1st and second left, we would fill up the 1st position and then for each such arrangement will enumerate the possibilities for filling up the only left out 2nd position. This is our fourth conclusion. But it gives rise to a new concept of forming permutations.

Rich concept: Flexibility in filling places: While following systematic Permutation enumeration, any sequence of positions may be filled up with the objects: Permutation placement flexibility principle

Filling up empty places of a permutation need not be carried out from left to right or right to left sequentially, it can be any sequence of positions as in abstraction essentially all positions are equivalent.

For example, while forming a 3 out of 4 permutation, it is not necessary that the 3 positions of a permutation are filled up from left to right or right to left. It can be any sequence. Depending on the problem need, we may decide to fill up the 1st right first, 3rd from right second and the middle position at the end. But the sequence must be same throughout the process of forming the permutation arrangements.

This holds because of independence of the positions with respect to each other. In other word, filling up the 3rd position won't affect filling up any other position except that one object will be reduced. This is true for filling up any position at any stage of forming the permutation arrangements.

Second stage of Enumeration of permutations:

In the second stage we would then take up filling up the  unit's place instead of expected ten's place.

In the unit's place three digits 0, 4, and 6 are possible when hundred's place has already been filled up with 5. For each of these, the left out ten's place can be filled up with left 3 digits, resulting in $3\times{3}=9$ possibilities. This is 3 less than 12 because of the restriction that 3 can't occupy the unit's position.

Third stage enumeration with 6 placed in 3rd position:

When 6 is placed in 3rd position, we can place in the unit's position only two digits 0 and 4 out of 0 ,3, 4 and 5 because of even number restriction. Each of these create 3 possibilities for the middle position, generating in total $2\times{3}=6$ possibilities.

Final result

Thus the total number of 3 digit even numbers greater than 500 formed out of the digits 0, 3, 4, 5 and 6 is, $9 + 6=15$.

Answer: c: 15

Concepts used:

Analysis of the problem revealed overlappping of occupancy restrictions because of digit 6 and thus the permutation process had to be split into two parts - use of problem breakdown technique.

Because of occupancy restriction on the 1st digit, after the 3rd digit, placement of digits started from 1st digit position instead of sequentially next, 2nd digit position -- use of full flexibility of sequence of populating positions while enumerating permutations methodically, rich concept of flexibility of filling places.

This is a rich concept and a powerful one.

Problem 3.

The sum of all the numbers that can be formed by using all the four digits 1, 2, 3 and 4 is,

  1. 65666
  2. 66660
  3. 66550
  4. 56650

Solution:

First conclusion from problem analysis:

The numbers will be 4 out of 4 permutation, that is $^4P_4 = 4\text{!} = 4\times{3}\times{2} = 24$.

Among these 24 numbers, there will be four groups of numbers with 6 numbers in each group and the digits 1, 2, 3 and 4 occupying the 4th position from right in each six numbers of the corresponding group.

Rich concept: Sum of permutations as sum of face values: Applying breaking up a number by face value technique

As this is problem of summing up 24 numbers, we break up each number as a sum of face values and then sum up 24 face values for each place, 24 face values of unit's place, 24 face values of ten's place, 24 face values of hundred's place and 24 face values of thousand's place.

A smaller example for explanation

Problem: Find the sum of all 3 digit numbers formed out of 1, 2, and 3.

Solution: As total number of the numbers is small, we will actually write down the permuted numbers:

$123 = 1\times{10^2} + 2\times{10} + 3$

$132 = 1\times{10^2} + 3\times{10} + 2$

$231 = 2\times{10^2} + 3\times{10} + 1$

$213 = 2\times{10^2} + 1\times{10} + 3$

$312 = 3\times{10^2} + 1\times{10} + 2$

$321 = 3\times{10^2} + 2\times{10} + 1$

The number of permutation is as expected, $^3P_3 = 6$.

Sum of numbers $=$ sum of face values of hundred's place + sum of face values of ten's place + sum of face values of unit's place

$= (1 + 1 + 2 + 2 + 3 + 3)\times{(10^2 + 10 + 1)}$

$= (1 + 2 + 3)\times{^2P_1}\times{111} $

$= 6\times{2}\times{111} $

$= 1332$

This simple result happens because, in each sum of face values we have 6 numbers with unique digits 1, 2 and 3 only and each occurring $^2P_1$ times. When we factor it out, we get effectively three factors in the sum, first: sum of the digits forming the numbers; second: $^2P_1$ which is the number of times a unique digit is repeated inside its group of numbers and third: sum of place values 111.

Rich concept: Extending the concept of summing up permutations formed from set of digits by sum of face values

For summing up permutations of numbers formed from 1, 2, 3, and 4 extending this rich concepts we can directly state the sum as,

$\text{Sum} = \text{(sum of 1, 2, 3, 4)}\times{^3P_2}\times{1111}$

$\hspace{12mm}= 10\times{6}\times{1111}$

$\hspace{12mm}= 66660$.

Again for summing up permutations of numbers formed from 1, 2, 3, 4 and 5 extending this rich concepts we can ditectly state the sum as,

$\text{Sum} = \text{(sum of 1, 2, 3, 4, 5)}\times{^4P_3}\times{11111}$

$\hspace{12mm}= 15\times{24}\times{11111} $

$\hspace{12mm}= 360\times{11111}$

$\hspace{12mm}= 3999960$.

Rich concept: Further generalizing sum of all numbers formed from, say, digits 2, 5, 6 and 7, freeing up the forming set from a sequence

The advantage of generalization or abstraction is, you change only the parameters affected by the change in ptoblem definition. The rest of the solution remains unchanged. So in this case the second and third factors will remain unchanged from our initial problem, only the sum of digits will change from, $(1 + 2 + 3 + 4) = 10$ to $(2 + 5 + 6 + 7)=20$ and the sum will just be the double of our previous result of 66660, that is, 133320.

Answer: b: 66660.

Concepts used:

Breaking up the numbers in the permutation to convert the sum of permutations to sum of face values -- a powerful use of Place value concepts.

Identifying that the unique digits appear same number of $^3P_2 = 6$ times in sum for each place of the 4 digit numbers formed.

This minor discovery enables us to express the desired sum as product of sum of the unique digits, 6 and sum of place values.

Sum of unique digits being 10, and sum of place values being always in the form of 1111, the final result turns out to be, $10\times{6}\times{1111} = 66660$.

Out of this analysis and clear understanding of the inherent mechanism of this type of problem structure, generalizing first to sum of numbers formed from any number of natural number 1 to 9.

Generalizing further by the use of powerful abstraction technique, ability to form sum of numbers formed from any set of digits out of the digits 1 to 9 (without any digit repeating).

Problem 4.

How many 3 letter words (may not be meaningful) can be formed with the letters of the word PENUMBRA each with at least one vowel?

  1. 388
  2. 276
  3. 150
  4. 212

Solution:

In the word PENUMBRA, there are 3 vowels A, E, U and 5 consonants. The problem definition stipulates at leasr one of the three vowels to appear in each of the target permutations.

Proceeding in a straightforward manner being too cumbersome we apply the set exclusion concept, in itself a powerful problem solving concept. It says,

When in a set of objects having a few properties, the subset having at least one property equals, all objects in the set minus the subset having none of the properties.

Effectively we exclude the subset having none of the properties from the whole set of objects to get the subset with each element having at least one property.

Rich concept: Applying set exclusion technique

In our problem total number 3 letter words possible = $^8P_3 = 8\times{7}\times{6} = 336$

And number of words with none of the three vowels is simply = $^5P_3 = 60$.

So desired number of 3 letter words with at least one vowel = 336 - 60 = 276.

Answer: b: 276.

Concepts used:

Rich concept of Set exclusion technique -- permutation.

Problem 5.

In how many ways can the letters of the word METRIC be arranged so that the two vowels are never together?

  1. 480
  2. 960
  3. 560
  4. 280

Solution:

In the 6 letter word METRIC, the two vowels are E and I and the rest 4 letters are consonants.

In this case also we will use the Set exclusion technique by finding the total number of permutations of 6 letters of METRIC first and then subtracing from it the permutations in which the two vowels appear together. That would give us the permutations in which the two vowels will never appear together.

So first conclusion: use of set exclusion technique.

To find number of permutations in which the two vowels appear together

When the two vowels appear together in any of the permutations we can assume them as a single character and find the permutations of 5 out of 5 characters,

$^5P_5 = 5\text{!} = 5\times{4}\times{3}\times{2} = 120$.

This is use of a standard technique of merging two or more objects into a single object in suitable situations.

Rich concept: Merging of two or more objects into a single object in permutations

So after merging the two vowels into a single couplet we obtained 120 number of six letter permutations in which the two vowels appear together as a couplet. But for each of these permutations, the two vowels can permute in $^2P_1 = 2$ ways, and so the actual number of six letter permutations in which the two vowels appear together is $2\times{120}$.

The total number of six letter permutations = $^6P_6 = 6{!} = 6\times{5\text{!}} = 6\times{120}$.

Thus the number of permutations of the letters of the word METRIC in which the two vowels never appear together is,

$6\times{120} - 2\times{120} = 4\times{120} = 480$

Answer: a: 480.

Concepts used:

Rich concept of Set exclusion technique -- Rich concept of merging of objects -- permutation.

Problem 6.

How many straight lines can be drawn from 15 non-collinear points?

  1. 110
  2. 105
  3. 115
  4. 120

Solution:

A straight line is formed from two points. As all the 15 points are non-collinear, that is, no three points are on a straight line, our problem is transformed to finding all Combinations of 2 out of 15, which is,

$^{15}C_2 = \displaystyle\frac{15\times{14}}{2\text{!}} = 105$

Answer: b: 105

Concepts used:

Basic linear Geometry concepts -- Combination.

Problem 7.

In how many different ways 5 boys and 5 girls can sit in a circular table so that the boys and the girls are alternately placed?

  1. 2800
  2. 2880
  3. 2400
  4. 2280

Solution:

This is a problem of circular permutation along with additional constraint. In a circular permutation problem, the technique is to fix any of the elements participating in the permutation at one position and then permute rest of the elements among the rest of the positions. This is the rich concept of circular permutation.

Rich concept: Circular permutation

In our problem out of 10 boys and girls we have fixed one boy $B0$ at 12'O Clock position and immediately the positions of the boys and girls became fixed because of the alternate requirements. This situation is shown in the following figure.

circular permutation

The five girls can be permuted within their allotted 5 positions in $^5P_5 = 120$ ways while the four boys can be permuted in left out 4 positions in $^4P_4 = 24$ ways, a total of, $120\times{24} = 2880$ ways.

Answer: b: 2880.

Concepts used:

Rich concept of Circular permutation -- permutation -- relating given condition and problem modeling.

Problem 8.

In how many ways a committee of 2 men and 3 women be formed out of a total of 4 men and 4 women?

  1. 15
  2. 20
  3. 16
  4. 24

Solution:

The selection of 2 men in $^4C_2 = 6$ ways is independent of selection of women in $^4C_3 = 4$ ways. So the total number of different ways the committee can be formed is, $6\times{4} = 24$.

Answer: d: 24.

Concepts used:

Independent selections -- Combination concepts.

Problem 9.

If there are 10 stations on a railway line, the number of different journey tickets to be printed by the railway authorities is,

  1. 45
  2. 91
  3. 90
  4. 93

Solution:

A ticket needs to be printed for a pair of stations, the starting station and the ending station. In a 10 station railway line number of such unique pairs is given by the permutation, $^{10}P_2 = 45$. That is easy. But here the problem won't end.

You need to consider downline journey tickets also. So finally the number of different types of tickets to be printed is, $45\times{2} = 90$.

Answer: c: 90.

Concepts used:

Problem formulation from a real world requirement -- Combination concepts -- basically it is permutation of 2 out of 10 as tickets for bothway journey are to be printed and ordering of a pair of stations is important. With this logic, without going through the Combination route we could have straightaway calculated the the required number using permutation.

Problem 10. 

A team of six is to be formed by taking two from each of three groups of boys numbering 5, 6 and 7. How many such teams are possible?

  1. 3150
  2. 3350
  3. 3250
  4. 4500

Solution:

The first step of expressing the possible number of teams is simply,

$^5C_2\times{^6C_2}\times{^7C_2} $

$\hspace{12mm}= \displaystyle\frac{5\text{!}\times{6\text{!}}\times{7\text{!}}}{2\text{!}\times{3\text{!}}\times{2\text{!}}\times{4\text{!}}\times{2\text{!}}\times{5{\text!}}}$

$\hspace{12mm}=\displaystyle\frac{6\text{!}\times{7\text{!}}}{8\times{3\text{!}}\times{4\text{!}}}$

$\hspace{12mm}=\displaystyle\frac{5\text{!}\times{7\text{!}}}{8\times{4\text{!}}}$

$\hspace{12mm}=\displaystyle\frac{5\times{7\text{!}}}{8}$

$\hspace{12mm}=5\times{7}\times{6}\times{5}\times{3}$

$\hspace{12mm}=3150$

Answer: a: 3150.

Concepts and comments:

This problem is a simple permutation of three independent sets, but the calculation is essentially time consuming and error prone. Using simplification techniques and delayed calculation technique of algebraic simplification, the calculation was done quickly and correctly.

 

Special note:

You will observe that for solving most of the problems, understanding the basic mechanism of forming a permutation or combination played more important role in solving the problems rather than routine formulas on permutation and combination.

Secondly, this topic is conceptually one of the more difficult topics covered in school maths. So our recommendation is to rely on conceptual base coupled with the set of rich concepts and problem solving solving strategies to solve any problem that may be encountered.