Suppose you have a set of:
- 5 Hats: H1, H2, H3, H4, H5
- 10 Pants: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10
- 6 Shoes: S1, S2, S3, S4, S5, S6
Suppose you have 3 Friends (F1, F2, F3).
- Each friend must at least pick one object
- Friends can pick similar combinations of objects
- However, no friend can have the exact same combination of objects as another friend
- After the 3 Friends have made their selections, items can still be left within the set
How many "Legal" Combinations can be selected from this set?
I have been trying to look at formulas that involve Factorials, Multinomial Theorem, Sampling With Replacement - but no formula seems to exactly match what I am trying to do.
Can someone please show me what formula needs to be used to solve this problem? And will there be a different formula if you want the set to be empty in the end?
Thank you!
Example of a Legal Combinations:
- F1:H1, H2, P1, S1, S2, S3
- F2: H1, H2, S1
- F3: P1, P5, S4, S5
Example of a Illegal Combinations: ( F2 = F3 )
- F1:H1, H2, P1, S1, S2, S3
- F2: H1, H2, S1
- F3: H1, H2, S1
Example of a Illegal Combinations: ( F1 contained in F2 )
- F1:H1, H2, P1, S1, S2, S3
- F2: H1, H2, P1, S1
- F3: H1, H2, S1
First, note that the type of items is irrelevant. Basically, there are 21 items.
Now expanding on the hint: Let us consider the case of two friends first. Friend 1 can select items in $n:=2^{21}-1$ ways, corresponding to the nonempty subsets of the set of total items. Call the set of ways as $A_1$. Friends 2 and 3 can similarly select items in $n$ ways also, denote the set of their ways as $A_2$ and $A_3$ (resp). By the product rule, the total number of ways the three friends can select items is $|A_1\times A_2\times A_3|=|A_1|\times |A_2|\times |A_3|=n^3$. This however includes the so-called 'illegal combinations' which must be subtracted now.
Clearly the number of ways of selections of friend $1, 2$ which are same are $n$ (as any of the $n$ selections can be identical). So there are $n$ illegal selections arising from selections of friends 1 & 2. Coupled with any of the $n$ selections of friend 3, by the product rule this means that there are $n^2$ illegal selections in which friend 1 and 2 choose identical items. Likewise there are $n^2$ illegal selections arising from friends 2,3 and there are $n^2$ illegal selections arising from friends 3 and 1. In total there are $3n^2$ illegal selections. We have however over-counted the illegal selections since we have included the $3n$ selections where all three pick the same items. These $3n$ selections arise in this fashion: In counting illegal selections of friends 1,2 we over counted $n$ selections where all three picked the same items, and likewise in the other two counts. These $3n$ selections must be treated as $n$ distinct selections and so the total number of illegal combinations is $3n^2-3n+n=3n^2-2n$, and the final required value is $n^3-3n^2+2n$.