If $A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}$. how many subsets are there?

Question

I have a question stating

Let $A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}$ be a set consisting of $n$ distinct elements. How many subsets does it have? How many proper subsets?

My thought is that there would be subsets with $1$ element, $2$ elements, $3$ element and so on, up to $n$ elements. The number of subsets of each size would be:

$$\begin{array}{c|c} \text{Subset size} & \text{no. of subsets} \\ \hline 1 & n \\ 2 & n-1 \\ 3 & n-2 \\ \vdots & \vdots \\ n-1 &n-(n-2) \\ n & n- (n-1) \end{array}$$ From this it seems the number of subsets would be $\displaystyle \sum_{k=0}^{n-1} (n-k) $. And for proper subsets, I would just not include the subsets of size $n$ , so $\displaystyle \sum_{k=0}^{n-2} (n-k) $. Is this correct?

Answer 1

I disagree. For example, the number of subsets of size 2 is $$ \binom{n}{2} = \frac{n(n-1)}{2} \ne n-1 $$ and in general you are looking at $$ \sum_{k=0}^n \binom{n}{k} = 2^n, $$ which is also easy to see from fundamentals by a simple counting argument -- each of the $n$ elements can be either included or excluded, independently of others. So you have $2$ choices $n$ times, a total of $2^n$.

Answer 2

Is a well-known fact that the answer is $2^n$. Proof by induction:

• $A_1 = \{x_1\}$ has two subsets: $\emptyset,A_1$.
• Suppose true up to $n$. The subsets of $A_{n+1} = \{x_1,\dots,x_{n+1}\}$ are the subsets of $A_n = \{x_1,\dots,x_n\}$ plus the subsets of $A_n$ union $\{x_{n+1}\}$.

Answer 3

Why do you think there will be $n-(k-1)$ subsets of size $k$?

Let's say you have a set of $25$ elements, $\{1,2,3,....., 25\}$ and you want is see who many subset of size $2$ there are.

You can have $\{1,2\}, \{1,3\}......, \{2, 25\}$. That's $24 = n- 1$. But those are all with the element $1$. What about subsets without the element $1$.

$\{2,3\}...... , \{2,25\}$ is $23$ and $\{3,4\}...\{3,25\}$ is $23$. and so on all the way to $\{24,25\}$ being $1$.

So adding those up we have $24 + 23 + 22 + ... + 1 = 300$.

But what about subsets of size $3$. $\{1,2,3\} ... \{1,2,25\}$ is $23$ and $\{1,3,4\}$ to $\{1,3,25\}$ is $22$ and $\{1,2,3\}...\{1,24,25\}$ is $23 + 22 + ... + 1 = 276$ and $\{2,3,4\}...\{2,24,25\}$ is $22 + .... + 1 = 253$. and so on so all of the subsets of size $3$ = \sum_{m=1}^{23} \sum_{i=1}^m i = \sum_{m=1}^{23} \frac {m(m+1)}2$.

And then to do subsets of size $4$ we get.... well, a headache.

A bit of thought is that choosing $k$ elements from $25$ (or $n$) is, quite literally choosing $k$ elements from $25$ (or $n$). So the number of subsets of size $k$ is ${n \choose k}$. Literally.

[This would imply that ${n \choose 3} = \sum_{i=1}^{n-2}\frac {i(i+1)}2$. Does it?]

So, anyway the number of proper subsets would therefore be: $\sum_{i=1}^{n-1} {n\choose i}$.

But... can that be simplified. You should play with that for about 14 hours or so.

$n =2\implies \sum{n\choose i} = 2$

$n = 3\implies \sum{n\choose i} = {3\choose 1 } + {3\choose 2} = 6$.

$n = 4 \implies \sum{n\choose i} = {4\choose 1} + {4\choose 2} + {4\choose 3} = 4 + 6 + 4 = 14$.

Notice anything?

Well, here's a suggestion. Try figuring the number of all subsets including the two improper subsets, $\emptyset$ and $A$.

Then the solution is $\sum_{i=0}^n{n\choose i}$.

Then the number of all subsets is

$n = 2; \sum {n\choose i} = {2 \choose 0} + {2\choose 1} + {2\choose 2} = 1+2+1 = 4$.

$n =3; \sum {n\choose i} = {3\choose 0}+ {3 \choose 1} + {3\choose 2} + {3\choose 3} = 1 + 3 + 3 + 1 = 8$.

And $n= 4; \sum {n\choose i} = {4\choose 0} + {4\choose 1} + {4\choose 2} + {4 \choose 3} + {4\choose 4} = 1 + 4 +6+ 4 + 1 = 16$.

Notice anything.

It seems that the number of all subsets is $2^n$.

Why would that be? We could probably prove $\sum_{i=0}^n{n\choose i} = 2^n$ by induction.... But what does it mean?

well, consider this single sentence:

For any of the $n$ elements of $A$, either the element is, or is not, in a specific subset of $A$.

Think about that. If we had considered that from the beginning, the whole thing could have probably been easier.

Answer 4

There are $${n\choose 0},{n\choose 1},...,{n\choose n-1},{n\choose n}$$ subsets from $\{x_1,...,x_n\}$ with no element, one element,..., $(n-1)$ elements, and $n$ elements respectively. Therefore the total number of subsets is $${n\choose 0}+{n\choose 1}+...+{n\choose n-1}+{n\choose n}=(1+1)^n=2^n$$