# Finding cardinality/possible combinations of sets

Problems:

Let $S = \{1, 2, 3, 4, 5, 6\}$.

(a) How many subsets are there of cardinality $4$? ($15$)

(b) How many subsets of cardinality $4$ have $\{2, 3, 5\}$ as a subset? ($\binom{3}{1} = 3$, but why $\binom{3}{1}$?)

(c) How many subsets of cardinality $4$ contain at least one odd number? ($\binom{6}{4} = 15$ but why does each subset contain at least one odd?)

(d) How many subsets of cardinality $4$ contain exactly one even number? ($\binom{3}{1}$, but why is this also $3$?)

I had no idea how to phrase the topic since I don't really understand what this is. I am having a difficult time with discrete mathematics. I understand how to get the answer to (a) by using pascal's triangle, but don't understand how to go about the other questions. I am at a loss right now, and I have an exam coming up quickly. Thanks for the help in advance.

• Do you know the relation between binomial coefficients and Pascal's triangle? Do you know what a binomial coefficient represents, and how to compute it? – TMM Oct 2 '16 at 2:53
• I understand that each coefficient is an element in a row of pascal's triangle. As for the rest I am at a loss of knowledge. – riderj Oct 2 '16 at 2:56
• For (b), just think how a four-element subset $T$ can contain $\{2, 3, 5\}$. Then clearly $T$ must also contain $2, 3, 5$ right? That leaves only one element of $T$ undecided, for which there are how many remaining elements in $S$? – TMM Oct 2 '16 at 3:07
• Question (b) indeed asks for subsets $T \subset S$ with $|T| = 4$ and $\{2, 3, 5\} \subset T$. So that leaves one element undecided. As three out of six elements from $S$ are already being used, that leaves $6 - 3$ options for the remaining $1$ element (or $3$ choose $1$). – TMM Oct 2 '16 at 3:15
• And you can also just list them all: $$\{2, 3, 5, 1\}, \quad \{2, 3, 5, 4\}, \quad \{2, 3, 5, 6\}$$ – TMM Oct 2 '16 at 3:16

How many subsets have cardinality $4$?
Since the set $S = \{1, 2, 3, 4, 5, 6\}$ has six elements, a four-element subset that contains the three-element subset $\{2, 3, 5\}$ must contain one element of the subset $\{1, 4, 6\}$. There are $$\binom{3}{1} = 3$$ ways of choosing one of those three elements. As TMM stated in the comments, the three resulting subsets are $$\{1, 2, 3, 5\}, \{2, 3, 4, 5\}, \{2, 3, 5, 6\}$$
How many subsets of cardinality $4$ contain at least one odd number?
Since the set $S$ contains three odd numbers and three even numbers, there can be at most three even numbers in a subset of size $4$. Therefore, at least one element in any four-element subset of $S$ must be odd. Since there are $$\binom{6}{4} = 15$$ four-element subsets of $S$, there are $15$ subsets of cardinality $4$ that contain at least one odd number.
How many subsets of cardinality $4$ contain exactly one even number?
If a subset of cardinality $4$ contains exactly one even number, then it must contain all three odd numbers and one of the three even numbers in set $S$. There are $$\binom{3}{1} = 3$$ ways of choosing one of the three even numbers in set $S$ to be the only even number in the subset of cardinality $4$. The three subsets that contain exactly one even number are $$\{1, 2, 3, 5\}, \{1, 3, 4, 5\}, \{1, 3, 5, 6\}$$