How many subsets contain $x_1$? How many subsets contain $x_2$ and $x_3$, but not $x_5$

combinatorics

Let $X = \{x_1,x_2,…,x_6\}$.

a) How many subsets of $X$ contain $x_1$?

b) How many subsets contain $x_2$ and $x_3$ but not $x_5$?

For (a) is the answer $32$ because $2^6 – 2^5 = 32$?

For (b) could I get tips on how to start? I don't know what to do.

Best Answer

Approach using the rule of product.

  • Pick whether or not $x_1$ is included in the subset
  • Pick whether or not $x_2$ is included in the subset
  • $\vdots$
  • Pick whether or not $x_6$ is included in the subset

Each of these will either have $2$ options (you do include or you don't include), or just one option according to the needs of the particular step of the problem you are on.

Multiply the number of options for each step together to get the total.

For part (a) you have only one option for what you do with $x_1$ since you are told you must include it. For all the rest you have two options available respectively. Meanwhile for part (b) you are told you must include $x_2$ and $x_3$ so these only have the one option of being included and $x_5$ you are told you must exclude so you have only one option for this as well while all others have two options each.

$~$

a) $1\times 2\times 2\times 2\times 2\times 2 = 2^5$

$~$

b) $2\times 1\times 1\times 2\times 1\times 2 = 2^3$

Related Question