Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is from the book Introduction to Topology and Modern Analysis by GF Simmons, Problem 3(d) at end of Section 1. I'll paraphrase the question here.

Suppose $U$ is a containing $n$ elements. Then, how many subsets are there? How many possible relations of the form $A \subseteq B $ exist where $A,\ B$ is a subset of $U$? Can you make an informed guess as to how many are true?

Solution:

First two are simple. $2^n$ and $2^{2n}$. For the third one, assume $A$ contains $k$ elements. Then, number of different possible $A$ is $\binom{n}{k}$ and the number of possible sets, of which $A$ is a subset, (number of different possible $B$) is $2^{n-k}$. Taking sum while varying $k$ from $0$ to $n$ gives us

$$\sum 2^{n-k} \binom{n}{k} $$

which is $3^n$. Is this correct? If it is? Then why does the book tells us to make an informed guess? Reading the word informed guess made me suspicious that the question is not as easy as it looks.

share|improve this question
    
"As easy as it looks" is in the eye of the beholder. Good analysis. –  André Nicolas Dec 3 '11 at 17:39
    
yeah... that's also true... –  Jayesh Badwaik Dec 3 '11 at 17:42
    
@Srivatsan: Thanks for the edit. Will keep the points in mind in the future! :) –  Jayesh Badwaik Dec 4 '11 at 15:07
    
@Jayesh I should've left a comment after editing. It's not to say that the notation $C(n,r)$ is not in use. However $\binom{n}{k}$ is much more common and standard these days. And it was designed with just the binomial coefficients in mind. :=) –  Srivatsan Dec 4 '11 at 16:44
    
:)... No problems.. You took out time to edit it.. That's enough! :) –  Jayesh Badwaik Dec 4 '11 at 18:59

1 Answer 1

up vote 3 down vote accepted

If $A \subseteq B$, then each element of $U$ can be

  1. in none of $A$ and $B$,
  2. in $B$ only,
  3. in $A$ and $B$.

The choices for each element are independent, so the answer is $3^n$.

share|improve this answer
    
ohh.. thats new!! thanks!! –  Jayesh Badwaik Dec 3 '11 at 17:39
    
Nice. Generalizes, too: there are $(k+1)^n$ true statements of the form $A_1\subseteq\dots\subseteq A_k$. –  Brian M. Scott Dec 3 '11 at 17:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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