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?

• Do you know how many subsets $\{1,2,3\dots , n\}$ has in total? – Jorge Fernández Hidalgo Apr 20 '16 at 20:41
• @CarryonSmiling $\{1,2,...,n\}$ has $2^n$ subsets. – Overclock Apr 20 '16 at 20:56

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

• 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? – Overclock Apr 20 '16 at 21:03
• @Overclock Yes. – JKnecht Apr 20 '16 at 21:12

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

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.

• very well-explained. Thanks! – NoviceProg Jan 20 '17 at 4:56

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.

• Yes, my mistake, thank you! – Merkh Apr 20 '16 at 20:55