3
$\begingroup$

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$.
1. How many subsets of size $2$ are there?
2.How many subsets are there altogether?

Answer:

1) I think there are $7$ subsets of size two are there, since $14$ elements$/2=7$ and also by grouping them into pairs it shows there are $7$ groups of pairs as follows; $\{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}, \{9,0\}, \{20,30\}, \{40,50\}\}$

2) I choose $15$, but I'm not sure.

However, are my answers valid? Hints are much appreciated.

$\endgroup$
  • 9
    $\begingroup$ There are $\binom{14}{2}$ subsets of size $2$. $\endgroup$ – André Nicolas May 22 '16 at 22:30
  • 2
    $\begingroup$ For example, your list is missing the subsets {2,3} and {8,20} and {8,30} and lots more.... $\endgroup$ – hmakholm left over Monica May 22 '16 at 22:31
  • 3
    $\begingroup$ The number of subsets is $2^n$, where $n$ is the number of elements of the whole set. $\endgroup$ – Ethan Hunt May 22 '16 at 22:32
  • $\begingroup$ what is the rule that says 2^n, where n is the number of elements of the whole sets, if that's the case then this must be for part 2 of the question? $\endgroup$ – Surdz May 22 '16 at 22:35
  • $\begingroup$ The answers below address your concerns :) $\endgroup$ – Irregular User May 22 '16 at 22:47
4
$\begingroup$

The comments have already very quickly pointed this out, but perhaps I can give an explanation on why they work.

$1$) André Nicolas' comment has already answered that there are $\binom{14}{2}$ subsets of size $2$. This notation is the binomial coefficient. That is, \begin{align}\binom{14}{2} &= \frac{14!}{(14-2)!2!}\\ &= \frac{14 \times 13 \times \color{red}{12} \times \color{red}{11} \times \color{red}{10} \times \color{red}9 \times \color{red}8 \times \color{red}7 \times \color{red}6 \times \color{red}5 \times \color{red}4 \times \color{red}3 \times \color{red}2 \times \color{red}1}{(\color{red}{12} \times \color{red}{11} \times \color{red}{10} \times \color{red}9 \times \color{red}8 \times \color{red}7 \times \color{red}6 \times \color{red}5 \times \color{red}4 \times \color{red}3 \times \color{red}2 \times \color{red}1)(2 \times 1)}\\ &=\frac{14 \times 13}{2}\\ &= 91. \end{align} This is correct because there are $14$ elements in your set, and we wish to choose $2$ of them each time.

$2$) Ethan Hunt's comment has already answered that there are $2^n$ subsets, including the empty set and the entire set itself. To find all subsets of a set, we take the power set of the set. It's easy to prove that the cardinality of the power set is $2^n$, where $n$ is the number of elements of the set. So in your case, there are $2^{14} = 16384$ subsets.

$\endgroup$
2
$\begingroup$

The total number of subsets of size $2$ is $\binom{14}{2}$. To understand this try to see how many ways are there to pick two distinct elements out of the set.

For the second part using the similar idea from the previous part, there are $\frac{14}{k}$ subsets with size $k$. So the total sum is:

$$\sum_{n=0}^{14} \binom{14}{n} = \sum_{n=0}^{14} \binom{14}{n}(1)^{14-n}(1)^{n} = (1+1)^{14} = 2^{14}$$

$\endgroup$
1
$\begingroup$

as Andre noted there are $ \binom{14}{2} $ ways to choose fourteen elements by picking two. we call this 14 choose 2. it is equal to $\frac{14!}{(12!)(2!)}$ check out Binomial Coefficient for more

the second part. is achieved by summing $ \binom{14}{n} $ from $n = 0$ to $n = 14$. it is Also the power set see Power Set and it has $2^{14}$ elements.

$\endgroup$
1
$\begingroup$

How many subsets of size $2$ are there?

Set $A$ has $14$ elements. In selecting a subset of size $2$, we have $14$ choices for the first element and $13$ choices for the second element. Thus, at first glance, it appears we have $14 \cdot 13$ possible subsets. However, the order in which the elements are selected does not matter. Selecting the element $1$ and then the element $2$ results in the same subset as selecting the element $2$ and then the element $1$ since $\{1, 2\} = \{2, 1\}$. Dividing by the $2! = 2$ orders in which two elements can be selected yields $$\frac{14 \cdot 13}{2}$$ subsets with two elements.

In general, if we wish to form a subset of $k$ elements from a set of $n$ elements, we have $n$ choices for the first element, $n - 1$ choices for the second element, $n - 2$ choices for the third element, and so forth until we are left with $n - (k - 1) = n - k + 1$ choices for the $k$th element. Hence, there are $$n(n - 1)(n - 2) \cdots (n - k + 1)$$ ways to make an ordered selection of $k$ elements. However, the same $k$ elements in the subset can be selected in $$k(k - 1)(k - 2) \cdots 1 = k!$$ orders. Thus, the number of subsets of size $k$ that we can select from a set with $n$ elements is $$\frac{n(n - 1)(n - 2) \cdots (n - k + 1)}{k(k - 1)(k - 2) \cdots 1} = \frac{n(n - 1)(n - 2) \cdots (n - k + 1)}{k!}$$ Multiplying the numerator and denominator by $(n - k)!$ yields $$\frac{n(n - 1)(n - 2) \cdots (n - k + 1)(n - k)!}{k!(n - k)!} = \frac{n!}{k!(n - k)!}$$ The number $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ is the number of subsets of $k$ elements that can be selected from a set with $n$ elements.

Hence, the number of subsets of set $A$ is $$\binom{14}{2} = \frac{14!}{2!12!} = \frac{14 \cdot 13 \cdot 12!}{2 \cdot 1 \cdot 12!} = \frac{14 \cdot 13}{2} = 91$$ as Andre Nicolas and others have indicated.

How many subsets are there altogether?

A subset of a set $S$ with $n$ elements is determined by which elements it includes. When forming a subset, we have two choices for each of the $n$ elements, to include the element in the subset or to not include it in the subset. Hence, a set $S$ with $n$ elements has $2^n$ subsets.

Since set $A$ has $14$ elements, it has $2^{14}$ subsets.

While it would be impractical to list all $2^{14} = 16,384$ subsets of set $A$, we can verify that the set $\{1, 2, 3\}$ has $2^3 = 8$ subsets. They are $$\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}$$

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