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$
  • $\begingroup$ Do you know how many subsets $\{1,2,3\dots , n\}$ has in total? $\endgroup$ – Jorge Fernández Hidalgo Apr 20 '16 at 20:41
  • $\begingroup$ @CarryonSmiling $\{1,2,...,n\}$ has $2^n$ subsets. $\endgroup$ – Overclock Apr 20 '16 at 20:56
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$
  • $\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 '16 at 21:03
  • $\begingroup$ @Overclock Yes. $\endgroup$ – JKnecht Apr 20 '16 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$
  • $\begingroup$ very well-explained. Thanks! $\endgroup$ – NoviceProg Jan 20 '17 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$
  • $\begingroup$ Yes, my mistake, thank you! $\endgroup$ – Merkh Apr 20 '16 at 20:55

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.