3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The answer is as gentle as instructive. +1 $\endgroup$ – Markus Scheuer Jul 6 '15 at 9:29
2
$\begingroup$

Well, there are $2^{18}$ subsets all in all. Of these, $\dfrac{18!}{9!\cdot 9!}$ have exactly $9$ elements. The rest either have more than $9$ or fewer than $9$. Now, by symmetry, the number of subsets with more than $9$ elements equals the number of subsets with fewer than $9$ (pair each subset with its complement). Thus the number of subsets with more than $9$ elements is $\dfrac{1}{2} \times \left(2^{18} - \dfrac{18!}{9!\cdot 9!}\right)$. Adding the number of subsets with exactly $9$ elements gives the desired result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.