Set Notation help?

Question

If $A=\{a_1,a_2,\dots,a_7\}$ and we want to know how many $3$ element subsets exist in $A$, would we simply use ${7\choose3}=35$ on a calculator, or does this notation not account for the empty set, in which case we would do ${8\choose3}=56$?

Answer 1

If you are looking for the proper three element subsets of $A$ then the answer is given $\binom{7}{3}$. Your intuition about the empty set is incorrect. When constructing the power set of a set, then we care about the empty set. However, there is no such element $\lbrace \rbrace$ in your set $A$.

Just as a side note, you should stray away from using your calculator on a computation like $\binom{7}{3}$. It does not allow you to critically think about the procedure at hand i.e. $\binom{7}{3}=\frac{7!}{3!(7-3)!}$. With this equality, you see that you have considered all possible ordered groups of size $7$, then have divided by groupings of $3$ where order matters, and likewise for $4$. What you are left with are groupings of three in which order does not matter.

Answer 2

A note to explain (hopefully) why you may have had this empty set in mind.

Let's count all subsets of a set with $n$ elements $S=\{a_1,a_2,\dots,a_n\}$.

As you have suggested, there are $n \choose k$ subsets with $k$ elements. It is easy to prove for $k>0$, and then remains the case $k=0$, which is conventionally $1$, since there is only one subset with no element at all, the empty set $\emptyset$.

Now, you may also count directly all applications from $S$ to $\{0,1\}$, and each application $f$ is equivalent to a subset of $S$ (the subset $A$ of values $x$ of $S$ such that $f(x)=1$). This function $f$ is also called the characteristic function of $A$ (in $S$).

And there are obviously $2^n$ such applications (for each $x$, you choose $f(x)=0$ or $1$), where only one is such that $f(x)=0$ for all $x$ (corresponding to the empty set).

Then the two ways of counting must be equivalent and

$$\sum_{k=0}^n {n\choose k}=2^n$$