1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – TMM Oct 2 '16 at 2:53
  • $\begingroup$ 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. $\endgroup$ – riderj Oct 2 '16 at 2:56
  • 1
    $\begingroup$ 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$? $\endgroup$ – TMM Oct 2 '16 at 3:07
  • 1
    $\begingroup$ 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$). $\endgroup$ – TMM Oct 2 '16 at 3:15
  • 1
    $\begingroup$ And you can also just list them all: $$\{2, 3, 5, 1\}, \quad \{2, 3, 5, 4\}, \quad \{2, 3, 5, 6\}$$ $\endgroup$ – TMM Oct 2 '16 at 3:16
1
$\begingroup$

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\}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.