Combinations

Question

How many number of 5 letter words that use letters from the 3 letter set {a,b,c} in which each letter occur atleast once?

Comments

is answer 36?

---

150?

---

correct if overcounting!

---

It should be onto functions from 5 places to 3 letters , right? 150

---

very good ! sushant

---

Number of onto functions from the set with n=4 elements to the set  with k=3 elements = k! * S2(4,3) = 3! 6 = 36 as can be seen here: https://gateoverflow.in/8212/gate2015-2_40
But here we have n = 3 {a,b,c}, and k = 5 {five lettered word}. We cannot have S2(3,5). So should we continue n = 5 and k = 3. I can see we get 150 if we take n = 5 and k = 3. But how can you justify to take n = 5 and k = 3 when its actually n = 3 and k = 5?

---

@Gate Aspirant 10.

This cant be solved by that methd. I would suggest dont always use the formula. Try logically first if possible.

---

Arjun sir has given two approaches on that page. First uses recurrence relation for S2(x,y). Second uses series for onto function (which essentially takes form of S(x,y)). Are you saying I should not use formula/recurrence relation in first approach? Even in 2nd approach of onto function, he has clearly stated following:

for onto function from a set A(m-element) to a set B(n-element) ,
should be hold " m >= n"

Is there any third approach?

---

This is difficult with recurrance. Try out simple things like method explained by Debashish.

Answer 1

total possible numbers with {a,b,c} = 3⁵

possible letter with {a,b} = 2⁵ (which includes aaaaa, bbbbb)

possible letter with {a,c} = 2⁵ (which includes aaaaa, ccccc)

possible letter with {b,c} = 2⁵ (which includes bbbbb, ccccc)

Required = all possible - possible only with ab, ac, bc

= 3⁵ - {2⁵ + 2⁵ + 2⁵ - 3} ; (3 bcz aaaaa, bbbbb, ccccc are occuring 2 times)

= 243 - (96-3)

= 150

Answer 2

To ensure at least one I will fill the three positions with a,b,c so it will be 3c1*2c1*1c1 = 3! =6 so now the rest two places can be filled in 3*3=9 ways ...So total ways will be 6*9=54 ways

Comments

150 is correct answer