How many distinct subsets of a set $\text{A}$ are there, containing at least $9$ elements, where the total number of elements in set $\text{A}$ is $18$ ?
I've solved it by making cases of either choosing $9$, $10$, $11$ and so on elements from the set and then adding them up, i.e, $$\sum_{r=9}^{18} \dbinom{18}{r} $$
However, the answer given in my book is $$\dfrac{1}{2} \times \dfrac{18!}{9! \cdot 9!} + 2^{17}$$
Although the numerical value of my answer and book's answer is equal, I'm interested in knowing the intended solution of the author.
The term $\dfrac{1}{2} \times \dfrac{18!}{9! \cdot 9!}$ is dividing $18$ elements into two equal parts. The term $2^{17}$ is the total number of subsets of a set containing $17$ elements. But I can't connect these two things with the question.
Any help will be appreciated.
Thanks.
P.S. If anyone is interested in knowing how I found $\displaystyle \sum_{r=9}^{18} \dbinom{18}{r} $ here is my method,
Let $\text{S} = \displaystyle \sum_{r=9}^{18} \dbinom{18}{r} $
By Binomial Theorem,
$2^{18} = (1+1)^{18} = \displaystyle \sum_{r=0}^{18} \dbinom{18}{r} $
$\implies 2\text{S} – \dbinom{18}{9} =2^{18} \left( \because \dbinom{18}{r} = \dbinom{18}{18-r}\right)$
and the rest follows.
Best Answer
If $A$ has $18$ elements, and $B\subseteq A$ has fewer than $9$ elements, then $B^c\subseteq A$ has more than nine elements. Also, if $B$ has more than $9$ elements then $B^c$ has fewer than $9$ elements. That means the number of subsets of $A$ with fewer than $9$ elements equals the number of subsets of $A$ with more than $9$ elements.
Of course, the complement of a set with $9$ elements is another set with $9$ elements. The number you want, the number of subsets of $A$ with at least $9$ elements, is almost half the number of all subsets of $A$. We can figure out just how close that almost is.
Let $m$ be the number of subsets of $A$ with more than $9$ elements, so $m$ is also the number of subsets of $A$ with fewer than $9$ elements. Let $n$ be the number of subsets of $A$ with exactly $9$ elements. Then you want to find $m+n$, and we can find it from the total number of subsets of $A$, which we'll call $t$.
$$\text{(fewer than $9$)+(exactly $9$)+(more than $9$)=(all)}$$ $$m+n+m=t$$ $$\begin{align} m+n&=\frac 12n+\frac 12t \\ &=\frac 12{18 \choose 9}+\frac 12\cdot 2^{18} \\ &=\frac 12 \cdot \frac{18!}{9! \cdot 9!} + 2^{17} \end{align}$$