calendarBack
Quant

/

Modern Maths

/

Permutations & Combinations
ALL MODULES

CAT 2025 Lesson : Permutations & Combinations - Special Types

bookmarked

3. Special Types

3.1 Combining Conditions

The following examples require us to use one or more of the above techniques.

Example 26

In how many ways can all the letters in the word FINANCE be arranged such that
(I) the two N's are never together
(II) the vowels occupy even places?
(III) the vowels occupy odd places?
(IV) all consonants are together
(V) the vowels are never together?

Solution

Case I: Total number of words = 7!2!\dfrac{7!}{2!} = 25202520

From this we can subtract the cases where Ns are always together. Here, we can treat the two Ns as 1 letter and permute the letters of the word. Now, we have F, I, A, C, E and NN (which is considered to be 1 letter).

Words where Ns are together = 6!6! = 720720

Number of words where Ns are never together = 2520−7202520 - 720 = 1800\boldsymbol{1800}

Case II: The 33 vowels (I, A, E) can occupy 33 even places (2nd, 4th and 6th letters) in 3!3! = 66 ways.

The remaining letters (F, N, N, C) can occupy the 44 odd places in 4!2!\dfrac{4!}{2!} = 1212 ways.

∴\therefore Total Permutations = 6×126 \times 12 = 7272

Case III: Condition is on 33 vowels occupying 33 of the 44 odd places. We can select the 33 odd places for the vowels in 4C3^{4} \text{C}_{3} ways and then permute the vowels in 3!3! ways. We can then assign the remaining letters (F, N, N, C) in 4!2!\dfrac{4!}{2!} ways.
∴\therefore Total Permutations = 4C3×3!×4!2!^{4} \text{C}_{3} \times 3! \times \dfrac{4!}{2!} == 4×6×124 \times 6 \times 12 =288= \boldsymbol{288}

Case IV: The consonants F, N, N and C can be treated as a single letter or block. Now, we have 4 letters/blocks – I, A, E, (FNNC). These can be permuted in 4! = 24 ways.

Within the block, F, N, N, C can be permuted in 4!2!\dfrac{4!}{2!} = 1212 ways.

∴\therefore Total Permutations = 24×1224 \times 12 = 288\boldsymbol{288}

Case V: When the vowels are never together, we can use the slotting technique (covered in Section 3.1).

Lets place the consonants (F, N, N, C) first ⇒ 4!2!\dfrac{4!}{2!} = 1212 ways

There are 55 slots between these consonants ( _F_N_N_C_ ), where the vowels can be slotted, so that they are not next to each other. We can now select the 33 slots and then arrange the vowels.

Number of ways to select 33 from 55 and arrange 33 vowels = 5C3×3!^{5} \text{C}_{3} \times 3! = 6060 ways.

∴\therefore Total Permutations = 12×6012 \times 60 = 720\boldsymbol{720}

Answer: (I) 18001800; (II) 7272; (III) 288288; (IV) 288288; (V) 720720


Example 27

A group of 77 students need to be seated in a row. Two students had a quarrel and, therefore, cannot be seated next to each other. In how many ways can the students be seated?

Solution

Permutations for 77 students can be seated = 7!7! = 50405040

If the 22 students are to be always together, they can be treated as one unit. So, 66 students/units to be permuted overall and within 11 one of the units, 22 of them to be permuted.
Permutations where the 22 are always together = = 1440

Permutations where the 22 are never together = 5040−14405040 - 1440 = 3600\boldsymbol{3600}

Alternatively

To slot the 22 quarrelling students, we first seat the 55 other students in 5!5! ways. We now have 66 slots between these 55 students and at the ends as shown below (where X represents a student seated and __ represents an empty slot).

__ X __ X __ X __ X __ X __

We can select these slots in 5C2^{5} \text{C}_{2} ways and permute the quarrelling students in 2!2! ways.

∴\therefore Permutations where the 22 are never together = 5!×6C2×2!5! \times ^{6} \text{C}_{2} \times 2! = 120×15×2 120 \times 15 \times 2 = 3600\boldsymbol{3600}

Answer: 36003600


3.2 Rank of a Word

Example 28

If all the letters in the word MATTER are permuted and arranged in alphabetical order, what is the rank of MATTER?

Solution

In these questions, we find the number of words that alphabetically occur before MATTER. Note that the only letter that is repeated is T, which occurs twice.

Words that start with Letters to be Permuted Number of Words
A MTTER 5!2!\dfrac{5!}{2!} = 6060
E MATTR 5!2!\dfrac{5!}{2!} = 6060
MAE TTR 3!2!\dfrac{3!}{2!} = 33
MAR TTE 3!2!\dfrac{3!}{2!} = 33
MATE TE 2!2! = 22
MATR TE 2!2! = 22
MATTER - 0!0! = 11


Rank = 60+60+3+3+2+2+160 + 60 + 3 + 3 + 2 + 2 + 1 = 131\boldsymbol{131}

Answer: 131131

Note: As we are finding the rank, we need to add the 1 way of writing MATTER as well.


3.3 Sum of Permuted Numbers

The following formula can be applied when we need to compute the total of all nn-digit numbers that can be formed using the given set of nn distinct digits, where none of the digits are zero.

The formula is derived from the following
1) Each digit appears in each of the digit places, i.e. place values, (n−1)!(n - 1)! times
2) [(n−1)!×(n - 1)! \times Sum of digits] provides the total of all the digits in each of the place values.
3) Sum of the place values of these numbers is 1+10+100+1 + 10 + 100 + ... =1111= 1111...n−digits_{n-digits}

Sum of all possible numbers =(n−1)!×= (n - 1)! \times sum of digits ×(111\times (111...n−digits)_{n-digits})

Example 29

What is the sum of all 44-digit numbers that can be formed with 3,4,53, 4, 5 and 66, where none of the digits are repeated?

Solution

Total numbers =4!=24= 4! = 24
Each of these digits will appear equal number of times in each of the digit places – units, tens, hundreds and thousands places.

Therefore, each of the units digits will appear equal number of times, i.e. 244=6\dfrac{24}{4} = 6 times in each of the places.

Sum of digits in the units place =(6×3)+(6×4)+(6×5)+(6×6)= (6 \times 3) + (6 \times 4) + (6 \times 5) + (6 \times 6) = 6×(3+4+5+6)=1086 \times (3 + 4+ 5+ 6) = 108

Therefore, in each of the digit places, the sum of digits (face values) will be 108108.

Sum of all the tens places =108×10=1080= 108 \times 10 = 1080
Sum of all the hundreds places =108×100=10800= 108 \times 100 = 10800
Sum of all the thousands places =108×1000=108000= 108 \times 1000 = 108000

Total value of the number =108000+10800+1080+108=119988= 108000 + 10800 + 1080 + 108 = 119988

Alternatively (Recommended) Sum of all the possible numbers =(4−1)!×(3+4+5+6)×1111=119988= (4 - 1)! \times (3 + 4 + 5 + 6) \times 1111 = 119988

Answer: 119988119988


There is a simple workaround that can be applied when 00 is one of the distinct digits. This is explained in the following example.

Example 30

What is the sum of all 55-digit numbers that can be formed with 3,4,5,63, 4, 5, 6 and 00, where none of the digits are repeated?

Solution

Sum of all possible 55-digit numbers including 0=(5−1)!×(3+4+5+6+0)×11111=47999520 = (5 - 1)! \times (3 + 4 +5 + 6 + 0) \times 11111 = 4799952

However, it is to be noted that when 00 occupies the ten-thousands place, the number becomes a 44-digit numbers. These numbers have also been added in the above result of 47999524799952.

Therefore, to eliminate these, we need to subtract the total of all numbers where 00 is in ten-thousands place. This is nothing but the 44-digit numbers that can be formed using 3,4,53, 4, 5 and 66.

Sum of all possible 44-digit numbers without 0=(4−1)!×(3+4+5+6)×1111=1199880 = (4 - 1)! \times (3 + 4 + 5 + 6) \times 1111 = 119988

Sum of all 55-digit numbers excluding 00 in ten-thousands place =4799952−119988=4679964= 4799952 - 119988 = 4679964

Answer: 46799644679964


3.4 Path Movement

In these questions, we need to take some steps or make some movements to reach a particular destination. The movements will be of two types, like left & up or front & back. We can use letters to represent these movements and then permute them.

Example 31

A person can either take a step forward or back. After taking 99 steps he has to be exactly 33 steps ahead of the point where he started. In how many ways can this be achieved?

Solution

To move exactly 33 steps ahead after taking 99 steps, one must take 6 forward steps and 33 backward steps. This can be in any order. Let the forward step be denoted by F and backward step be denoted by B.

FFFFFFBBB denotes the person has taken 66 forward steps to begin with and then has taken 33 backward steps.
However, other combinations like FFBBBFFFF or FBFBFBFFF are also possible.

Number of ways in which FFFFFFBBB can be permuted is the number of ways we need to find.

Permutations of the word FFFFFFBBB =9!6!×3!== \dfrac{9!}{6! \times 3!} = 9×8×73×2×1=84\dfrac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84

Answer: 8484


Example 32

In the image below, the vertical and horizontal lines represent the roads in a city. At points of intersection, one can move from one road to the other. Mary has to travel from points A to B taking the shortest possible path.
(I) In how many ways can she travel from A to B?
(II) In how many ways can she travel from A to B if she has to pass through point C, where she picks up her kid from school?


Solution

Case I: Horizontal lines are parallel to one another. Likewise, the vertical lines are also parallel.

Let a movement upwards be denoted by U and the movement rightwards be denoted by R.

The shortest route, irrespective of the order, comprises of 55 Us and 55 Rs. One such path is UUUUURRRRR.

UUUUURRRRR can be permuted in 10!5!×5!=252\dfrac{10!}{5! \times 5!} = \bm{252} ways

Case II: The shortest path from A to C should have 22 Us and 22 Rs

UURR can be permuted in 4!2!×2!=6\dfrac{4!}{2! \times 2!} = 6 ways

The shortest path from C to B should have 33 Us and 33 Rs.

UUURRR can be permuted in 6!3!×3!=20\dfrac{6!}{3! \times 3!} = 20 ways

Shortest way to travel from A to C and then from C to B =6×20=120= 6 \times 20 = 120 ways

Answer: (I) 252252; (II) 120120

Note: The word and highlighted above clearly requires us to multiply the ways. Note that for every 11 way from A to C, there are 2020 ways from C to B. As there are 66 ways from A to C, one can go in 6×20=1206 \times 20 = 120 ways from A to B via C.


Loading...Loading Video....