GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 11

Question

Professor Nalanda has $6$ distinct properties which he decided to distribute among his $4$ daughters. He hires a consultancy firm for the same which charges Rs. 100 for each of the possible distribution assuming each daughter gets at least one property and all daughters being considered distinct. How much fee will Professor have to pay the agency (in multiples of 100)?

Answer 1

This is a balls-in-bins problem where both balls and bins are distinct and no bin should be empty. If bins can be empty, the solution is given by $4\times 4 \times 4\times 4\times 4\times 4 = 4^6$ as each of the $6$ property can go to any of the $4$ daughters. Now from this we have to subtract the cases where some daughters are not getting any property which can be done by Inclusion-Exclusion Principle as follows:

First we will subtract (exclude) the cases where one daughter is not getting any property. Then we will add (include) the cases where 2 daughters are not getting any property (this was already subtracted in the earlier case). Then we will again subtract (exclude) the cases where 3 daughters are not getting any property. Now we are done as there is no option of $4$ daughters not getting any property.

So, our required answer $ = 4^6 - {}^4C_1 \times 3^6 +{}^4C_2 \times 2^6 - {}^4C_3 \times 1^6 $

$\qquad = 2^{12} - 4 \times 729 + 6 \times 64 - 4$

$\qquad =4096 - 2916 + 384 - 4$

$\quad = 1560.$

Comments

Question says “in multiple of 100”

---

Okay sir got it !

---

same as number of onto functions.