0

Suppose I have Set A of 10 items, Set B of 8 items, and Set C of 40 items. How do I calculate the different combinations assuming at least one of Set A must be selected? None of the items can be duplicated.

For example, one combination can be: Item 1 of SetA, Item 3 of SetA, and Item 35 of SetC.

Another example: Item1 of SetA

Example 3: Item 9 of SetA, Item 30 of SetC, Item 35 of Set C, Item 39 of Set C

How would it change if you didn't have to select one of Set A?

ono
  • 121
  • Are items distinguishable? For example, is item 2 of A, item 7 of A, item 16 of C the same "combination" as your first example, or is it different? – David Apr 23 '14 at 01:24
  • 1
    All the items are unique – ono Apr 23 '14 at 01:25

2 Answers2

1

A power set of a set A is defined as the set of all of the subsets of A. I think this is what you are looking for. (i.e. $P(A)$ is the power set of A). The size of $P(A)$ is equal to 2 to the power of the size of set $A$, so $|P(A)|=2^{|A|}$

Keeping this in mind, $$P(B)=2^{|B|}=2^8\\P(C)=2^{|C|}=2^{40}\\P(A)=2^{|A|}=2^{10}$$ But we don't want to include the empty set from $P(A)$, so $P'(A)=P(A)-1=2^{10}-1$

This makes the total number of combinations=$$(2^{10}-1)(2^8)(2^{40})=2^{58}-2^{48}$$

This might also be some help: Power Sets Cardinality Proof

Using the same strategy from above, if no restriction was placed, then the total number of combinations would just be $2^{58}$

Sidd Singal
  • 3,452
1

The total number of selections is $2^{58}$, and this is the answer to your second question, as long as it is permitted to select nothing at all.

The number of selections with nothing from A is $2^{48}$, so the answer to your first question is $2^{58}-2^{48}$.

Edit. If you factorise this you can confirm that it is the same as @mathguy's answer.

David
  • 82,662