Question

Set A has elements 1, 2. Set B has elements a, b, c, d. We're interested in making subsets from the product of A x B that have at least 3 elements. How many subsets can be made?

Answer 1

219

Explanation:

Let's let `A={1,2}` and `B={a,b,c,d}`

When we take `A xx B`, what we're saying is that we end up with a set where each element is in the form of `(a,b)` where each element in `A` and each element of `B` are listed. For instance, in the example above, the list of the elements of `AxxB` are:

`{(1,a),(1,b),(1,c),(1,d),(2,a),(2,b),(2,c),(2,d)}`

And so we have a set with eight elements.

Now from this, we want to set up subsets that have 3 or more elements. The order of choosing the elements doesn't matter, and so it'll be a combinations calculation.

The general formula for a combination is:

`C_(n,k)=(n!)/((k!)(n-k)!)` with `n="population", k="picks"`

We're interested in 3 or more in the subset, so we have to sum up each one (those with 3, those with 4, etc):

`C_(8,3)=(8!)/((3!)(8-3)!)=(8!)/((3!)(5!))=56`

`C_(8,4)=(8!)/((4!)(8-4)!)=(8!)/((4!)(4!))=70`

`C_(8,5)=(8!)/((5!)(8-5)!)=(8!)/((5!)(3!))=56`

`C_(8,6)=(8!)/((6!)(8-6)!)=(8!)/((6!)(2!))=28`

`C_(8,7)=(8!)/((7!)(8-7)!)=(8!)/((7!)(1!))=8`

`C_(8,8)=(8!)/((8!)(8-8)!)=(8!)/((8!)(0!))=1`

`56+70+56+28+8+1=219`