Question

In how many ways can 8 different dolls be packed in 5 identical gift boxes such that no box is empty if any of the boxes hold all of the toys?

(a) 2351

(b) 365

(c) 2740

(d) 1260

This question was posed to me during an interview.

The origin of the question is Counting topic in division Counting of Discrete Mathematics

Answer 1

The correct option is (d) 1260

For explanation: Dolls are different but the boxes are identical. If none of the boxes is to remain empty, then we can pack the dolls in one of the following ways:

     Case i. 2, 2, 2, 1, 1

     Case ii. 3, 3, 1, 1

Case i: Number of ways of achieving the first option 2, 2, 2, 1, 1. Two dolls out of the 8 can be selected in ^8C2 ways, another 2 out of the remaining 6 can be selected in ^6C2 ways, another 2 out of the remaining 4 can be selected in ^4C2 ways and the last two dolls can be selected in ^1C1 ways each. However, as the boxes are identical, the two different ways of selecting which box holds the first two dolls and which one holds the second set of two dolls will look the same. Hence, we need to divide the result by 2. Therefore, total number of ways of achieving the 2, 2, 2, 1, 1 is = (^8C2 * ^6C2 * ^4C2  * ^1C1  * ^1C1) / 2 = 1260.