GATE CSE 2020 | Question: 42

Question

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.

Comments

I have tried using mutual inclusion - exclusion here but it seems to not work here . Can anyone point out why ? Here’s what i did

N(L,I,A,C not in their place) = N(total permutation) – N(either L or I or A or C is in it’s own position)

For finding N (I or L or A or C ) i have used mutual inclusion exclusion in the following way

= N (I in place ) + N(L in place) + N(A in place) + N(C in place) – N (L and A in place) – N(L and I in place) – N(L and C in place) – N(A and C in place) – N(A and I in place) – N(I and C in place) + N( L , I , A in place) + N(L , A , C in place) + N(I , A , C in place) + N(L , I , C in place) – N(L , I , A , C in place)

= 4!/2! + 3! + 4!/2! + 4!/2! – 2! – 2! – 2! – 3!/2! – 3!/2! – 3!/2! + 1 + 1+ 1 + 1 – 1

= 30

So N (L,I,A,C no in place) = 5!/2! – 30 = 60 – 30 = 30

Can anyone point out where my understanding went wrong ?

---

For n size word, If all letters are different –

no of arrangements so that the letters are not in their original places is = (n-1)!  // as 1 slot cannot be taken

Now we got permutations = (n-1)! , So if 2 letters are same then, (n-1)!/2!

---

There are 3 choices for the first slot, and then 2 for the third slot. That leaves one letter out of I,A,C unchosen and there are 2 slots that one might occupy. After that, the L′s must go in the 2 unfilled slots.

Hence the answer is,

3×2×1×2 = 12 

Source: G4G

---

@Deepak Poonia Sir why this question cannot be solved using derangements i.e 

!n which denotes subfactorial of n??

---

@abir_banerjee derangement formula is applicable when all the object and boxes are distinct .

Here the object which is the characters are identical “L” appears twice but boxes which means the positions are distinct .So we cant apply the formula directly.

---

@abir_banerjee

Watch the following “Derangement” Lecture. This question & its variations have been covered in detail.

https://www.youtube.com/watch?v=Ut-eDWWISkE&t=2431s

---

thanks sir

---

First in the places of 2 L we can place AC, IC , AI (each one of the pair in 2 ways like AC as CA)

we need to arrange the remaining 3 letters in 3 places we can consider the 2 L as one so remaining 3 letters can be arranged in 2! ways then the answer will be (2+2+2)*2 = 12  correct me if wrong  @Deepak Poonia sir

---

https://youtu.be/lblWHVLJc0A?t=3757

Answer 1

We have $\text{LILAC}$.

Lets number the positions as $1,2,3,4,5$. Now the two $L$s cannot be placed at position $1$ and $3$ but they can be positioned at $2,4,5$ in $^3C_2= 3$ ways. (since the $Ls$ are indistinguishable)

Now one of $2,4,5$ is vacant. Without loss of generality lets say $2$ is vacant.

Now, if $2$ is vacant we can't palce $I$ there but we can place any of $A$, or $C$, so we have $2$ choices for the position which is left after filling the two $Ls$. Now all of $2,4,5$ are filled.

For the remaining two places $1,3$ we have two characters left and none of them is $L$ so we can place them in $2! = 2 $ ways.

Multiply them all = $^3C_2 * 2 * 2! = 3 * 2 * 2 = 12  \ (ans)$.

Comments

okay so we have a standard formula for this ..got it...thanks.

---

nice explaination

---

if elements are distinct: follow the recurrence relation

Dn = (n-1) * (Dn-1 + Dn-2)  the relation is intuitive keep one element at  n-1 positions and that kept position original element comes to our position then reduces to Dn-2 problem else Dn-1

so D1 = 0 (since we can't keep a element other than its position)

D2 = 1 (only one way to interchange the elementss)

just calculate upto your required n (only if ther are distinct_

Answer 2

Problems like these can be solved by taking cases 

Comments

clear explanation...as compared to other answers

---

best and easy to understand answer

 

Answer 3

Word is LILAC-

In 1st position A, C and I can come.

Let's start with I - if I comes in 1st position you have 3 choices for 2nd position that are L, A, and C. Now fix L, two choices for 3rd position A and C. If you keep applying this end result would be 

for starting with I

ILACL

ILCLA

IACLL

ICALL

for starting with A

ALICL

ALCIL

ALCLI

ACILL

for starting with C

CLAIL 

CLALI

CLILA

CAILL

So, there are total 12 permutations.

Comments

When the question ∈ (P-Problem) and not (NP- Problem), most of the times, Brute Force is safer and faster than any knowledge of combinatorics.

---

But sadly not creative enough to solve for when word length gets big.

---

in some questions not being creative is the key to solve the problem within 2 minutes, cause at the end of the day you just need the answer to be correct

Answer 4

I think This would help

https://www.youtube.com/watch?v=ZT8zBvCr7L8

Also to know about " ! n "

https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/

Answer 5

Answer: 12

Explanation

Here, none of the characters can be at their respective positions in any permutation and we have 2 indistinguishable character- 'L',. Since there are very few characters (5 here) with repeating 'L', we can fix possible positions of 'L' and check. You'll find there are only 3 such possible positions-
1. _ L _ L _
2. _ L _ _ L
3. _ _ _ L L
 

For simplicity, take case 1 and we can conclude that there will be 6 possible strings (3x2x1) which will be-
I L A LC   //NOT ACCEPTABLE SINCE C is at it's correct position
I L C L A
A L C L I
A L I L C    //NOT ACCEPTABLE SINCE C is at it's correct position
C L A L I
C L I L A

This leads us to 4 permutations in one such permutation by fixing L.

Similarly there will be 4 such strings in each of the 3 fixed L cases.

Hence total permutations = 4 + 4 + 4 = 12 (or say 4x3)

Answer 6

Video Solution

https://www.youtube.com/watch?v=X07pj-9KEwM

 

L I L A C

!1 = 0

!2 = 1

!3 = 2(1+0) = 2

!4 = 3(2+1+ = 9

!5 = 4*(9+2) = 44

As $!n = (n-1)[!(n-1)+ !(n-2)]$

Number of ways we can put each alphabet at different place will be !5 i.e. 44

but we have to consider all the cases below

CASE 1: if first L goes in second L’s shoes that means !4 ways are there as I dont care where the second L is

CASE 2: IF second L goes in First L’s shoes that means !4 ways are there as I dont care where the first L is

CASE 3: if First L and Second L swap there place then we have !3 ways of arranging IAC

 

All these cases have to be subtracted from !5

And as we have 2 L’s then we did counting twice, so we will divide by 2!

Ans =  $\frac{!5-!4-!4-!3}{2!}$

which is $\frac{44-9-9-2}{2}=12$

 

 

 

Comments

Then it is very easy,

answer would be 44.

---

how bro? please explain.I think there would be intersections amongst.

---

If all the elements are distinct then we can use the formula of dearrangement If word is LIZAC 

n=5

5!(1/1! + 1/2! - 1/3! + 1/4! - 1/5! )

Then answer would be 44