How to find the number of subsets of any given set that contain a particular number
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$ 24 Answers
$\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$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$ $\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$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
