Permutation and Combination

Permutation and Combination:

Factorial Notation
Basic Principles of Counting
Permutations
Restricted Permutations
Combination in Math
Restricted Combinations

There are some cases where after making different types of possible selections, arrangements of the objects in each selection are also to be considered. Problems connected to word-making, boat crew, etc. are of this type. Some of the related problems are discussed below.

Example 1: In how many ways can the letters of the word PROPORTION be arranged by taking 4 letters at a time?

Solution- The number of letters in the word PROPORTION is 10 in which there are 3 O’s, 2 R’s, and 2 P’s. Now the selection of four letters from 10 letters can be done in the following ways.

(I) 3 alike letters and 1 distinct letter.
(II) 2 alike letters and 2 different letters.
(III) 2 alike letters of one kind and 2 alike letters of other kinds.
(IV) All four are distinct letters.

(I) 3 alike letters and 1 distinct letter. There is only one set of three alike letters (i.e.) O, O, O so three alike letters can be selected in 1 way. Now out of the remaining five distinct letters i.e. P, R, I, N, T one letter can be selected in ⁵C₁ ways. Thus 3 alike letters and 1 distinct letter can be selected in 1 x ⁵C₁ = 5 ways.

Now in each way, the four letters in which three are alike can be arranged in 4!/3! = 4. Thus the total number of words consisting of 3 alike and 1 distinct letter = 5 x 4 = 20.

(II) Two alike letters and two distinct letters. There are three sets of two alike letters from which one set can be selected in ³C₁ ways. Now from the remaining five distinct letters, two letters can be selected in ⁵C₂ ways. Thus the number of ways of selecting 2 alike and 2 distinct letters = ³C₁ x ⁵C₂ = 3 x 10 = 30. Now in each way, four letters out of which two are alike can be arranged in 4!/2! = 12. Thus the total number of ways of forming words in which two are alike and two are distinct = 12 x 30 = 360.

(III) 2 alike of one kind and 2 alike of other kinds. There are three sets of two alike letters in which two sets can be selected in ³C₂ ways. Thus the number of ways of selecting 2 alike letters of one kind and 2 alike letters of other kind is ³C₂ = 3. Now in each way four letters out of which two alike of one kind and two of other kind = (4! / 2! 2!). Thus, the number of words consisting of 2 alike letters of one kind and 2 alike letters of other kind = 3 x 6 = 18.

(IV) All four are distinct. The number of distinct letters = 6, out of which 4 can be selected in ⁶C₄ ways. Thus, the number of ways of selecting all distinct letters = ⁶C₄ = ⁶C₂ = 15. Now in each way, all four distinct letters can be arranged in 4! ways = 24. Thus, the total number of words consisting of four distinct letters = 24 x 15 = 360.

∴ Total number of ways = 20 + 360 + 18 + 360 = 758

Example 2: A boat’s crew consists of 12 men, 4 of whom can only row on one side and 2 only on the other side. In how many ways can the crew be arranged?

Solution- 4 of the crew can row on one side and 2 only on the other side. Clearly, the remaining (12 – 4 – 2) i.e. 6 of the crew can row on both sides. Now, in a 12-oared boat, there will be 6 crew on one side. Accordingly, we are to select 2 persons for the side having already 4 and the rest will go to the other side. Now, 2 persons from the remaining 6 can be selected in ⁶C₂ ways. There will now be 6 persons on one side and 6 of the crew on each side can be arranged in 6! ways. Therefore, the required number of arrangements in this case = ⁶C₂ x 6! x 6! = (6 x 5 / 2) x 720 x 720 = 7776000.

Example 3: How many 4 digit numbers can be formed from the digits 1, 1, 2, 2, 3, 3, 4, and 5?

Solution: The given digits are (1, 1), (2, 2), (3, 3), 4, and 5. The various choices by taking 4 digits at a time are:

(i) two pairs of alike digits.
(ii) one pair of alike digits and 2 different.
(iii) all four different digits.

The number of selections are:

(i) ³C₂ = 3
(ii) ³C₁ x ⁴C₂ = 3 x (4 x 3 / 2) = 18
(iii) ⁵C₄ = 5

To get the different numbers, we are to arrange the digits in all the above cases. Obviously, the number of numbers in the above cases are:

(i) 3 x (4! / 2! 2!) = 18
(ii) 18 x (4! / 2!) = 18 x 12 = 216
(iii) 5 x 4! = 5 x 24 = 120

Thus, the total number of numbers in this case = 18 + 216 + 120 = 354

Example 4: A tea party is arranged for 16 people along two sides of a long table with 8 chairs on each side. 4 men wish to sit on a particular side and two on the other side. In how many ways can they be seated?

Solution: Having seated 4 men on one side and 2 men on the other, there are 10 persons remaining. Out of those 10 men, 4 are to be chosen for the side containing the 4 persons already seated which can be done in ¹⁰C₄ ways. For the other side, however, there are no more selections as six persons are then remaining who are to be seated there. Now, 8 persons on each side can be arranged in 8! ways. Hence, the required number of seating arrangements in this case = ¹⁰C₄ x 8! x 8!.