4
$\begingroup$

Given a set $\{1,2,...,n\}$, how would one go about finding the number of subsets that contain the number 2, for example.

Having had a play around with this myself I've got as far as realising that the number of sets that contain the number $n$ is $2^{n-1}$, but this was only through listing out the power sets of a few sets and seeing how many subsets contained the last element of the set. A messy and very unreliable method, I'm sure you'll agree.

Say if I had the set $\{1,2,3,4,5\}$ and I wanted to know how many subsets within the power set contained the element 3, would I have to list out the entire power set and risk making a fatal mistake or is there some sort of a formula that will provide me with an answer?

$\endgroup$
2
  • $\begingroup$ Do you know how many subsets $\{1,2,3\dots , n\}$ has in total? $\endgroup$
    – Asinomás
    Apr 20, 2016 at 20:41
  • $\begingroup$ @CarryonSmiling $\{1,2,...,n\}$ has $2^n$ subsets. $\endgroup$
    – Overclock
    Apr 20, 2016 at 20:56

4 Answers 4

5
$\begingroup$

Pick out the number $2$ so you are left with the

set $\{1,3,4,...,n\}$. Now you construct all subsets of

this set and add a $2$ to each of these subsets.

As $\{1,3,4,...,n\}$ is a set of $n-1$ elements

it has in total $2^{n-1}$ subsets and by your

construction you have in total $2^{n-1}$ subsets

of $\{1,2,3,...,n\}$ that contains a $2$.

$\endgroup$
2
  • $\begingroup$ So from this I would assume that to find the number of subsets that contain any element from an $n-$element set, $A$, you simply compute $2^{n-1}$, and this would hold true for any element in $A$ . So for a $5-$element set each element appears occurs in 16 subsets, correct? $\endgroup$
    – Overclock
    Apr 20, 2016 at 21:03
  • $\begingroup$ @Overclock Yes. $\endgroup$
    – JKnecht
    Apr 20, 2016 at 21:12
3
$\begingroup$

Hint: there is a one-to-one correspondence between the subsets of $\{1,..,n\}$ which contain $n$ and the subsets of $\{1,...,n-1\}$

$\endgroup$
2
$\begingroup$

Having had a play around with this myself I've got as far as realising that the number of sets that contain the number $n$ is $2^{n−1}$, but this was only through listing out the power sets of a few sets and seeing how many subsets contained the last element of the set. A messy and very unreliable method, I'm sure you'll agree.

I couldn't disagree more! What you've almost stumbled upon is a very elegant way to answer your question...namely, using binary!

Let's say we have a bitstring of length $n$. Let's denote the $i$-th bit by $0$ if we exclude the $i$th element in a given set and $1$ if we include it.

As an easy example, let's say our set is $\{p,q,r\}$, which has 3 elements. Then the subsets corresponding to the power sets would have a total of $2^3$ possibilities:

$$ \{ \} \to 000 \\ \{r \} \to 001 \\ \{q\} \to 010 \\ \{q,r\} \to 011 \\ \{p\} \to 100 \\ \{p,r\} \to 101 \\ \{p,q\} \to 110 \\ \{p,q,r\} \to 111 .$$

You can be sure we've hit every subset since there are $2^3=8$ subsets. In particular, we count the empty set $\{ \}$ and the entire original set (which corresponds to bitstrings of all $1$'s).

Anyway, what you want is the number of subsets that contain a particular value, say $i$, from the power sets. This corresponds exactly to the number of bitstrings of length $n$ with a $1$ for the $i$th bit! Since we have 2 choices for the first bit, 2 choices for the 2nd bit, ..., 2 choices for the $(i-1)$st bit, 2 choices for the $(i+1)$st bit, ..., 2 choices for the $n$th bit, we have a total of $2^{n-1}$ desired bistrings.

$\endgroup$
1
  • $\begingroup$ very well-explained. Thanks! $\endgroup$
    – NoviceProg
    Jan 20, 2017 at 4:56
2
$\begingroup$

Lets say your set is $\{1,2,3,4,5\}.$ You want the number of sets that contain 3.

The formula you seek is $2^4$ in this case. Why?

Well on one hand, you can write them out, find that there are:

1 set of size 5,

4 sets of size 4,

6 sets of size 3,

4 sets of size 2,

1 set of size 1,

which is just $\sum_{k = 0}^4 {4 \choose k} = 2^4.$ Think of pascal's triangle.

This easily generalizes to any finite size set.

$\endgroup$
1
  • $\begingroup$ Yes, my mistake, thank you! $\endgroup$
    – Merkh
    Apr 20, 2016 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .