There are 15 cloths that need to be packed into 3 bags, with the mandate that…
There are 15 cloths that need to be packed into 3 bags, with the mandate that each bag must contain at least one cloth. In how many ways can the bags be filled?
Answer: 91 — Concept (stars and bars, at-least-one-each case): the number of ways to distribute n identical items into k distinct groups, with every group required to…
Attempted by 4 students.
Show answer & explanation
Correct answer: 91
Concept (stars and bars, at-least-one-each case): the number of ways to distribute n identical items into k distinct groups, with every group required to receive at least one item, equals n-1Ck-1. This is derived by first placing one item in every group (using up k items) and then distributing the remaining (n - k) items among the k groups with no lower-bound restriction, which is the standard unrestricted stars-and-bars count (n-k)+k-1Ck-1.
Let x, y and z be the number of cloths placed in bag 1, bag 2 and bag 3 respectively, so x + y + z = 15, with x, y, z >= 1 since every bag needs at least one cloth.
Give one cloth to each bag first. This uses 3 cloths, leaving 15 - 3 = 12 cloths still to be placed.
The remaining 12 cloths can now go into any bag with no lower-bound restriction, so count the non-negative integer solutions of x' + y' + z' = 12.
By stars and bars, the number of non-negative integer solutions of a sum of 3 variables equal to 12 is 12+3-1C3-1 = 14C2.
Compute 14C2 = (14 x 13) / 2 = 91.
Cross-check: applying the direct at-least-one-each formula n-1Ck-1 with n = 15, k = 3 gives 14C2 = 91 as well, confirming the two-step derivation above.
So the bags can be filled in 91 ways.