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.

Question-> Let $S$ be a set of $n$ consecutive natural numbers. How to find the number of ordered pairs $(A,B)$, where $A$ and $B$ are subsets of $S$ and $A$ is a proper subset of $B$.

Number of subsets -> $2^n$ --> here $2^8$ number of proper subsets -> $(2^n)-1$

then how the answer is $3^n-2^n$ ?

Please explain..

share|improve this question
    
Wow, I have a deja vu. I feel like this exact question was posted a year or two ago. –  Asaf Karagila Jun 26 '13 at 6:00
add comment

3 Answers 3

Consider the complement.

Hint: There are $2^n$ pairs of subsets where $A = B$, which is a subset of $S$.

This follows from the rule of product, because there are 2 possibilities for each element.

Hint: There are $3^n$ pairs of subsets where $A$ is a subset of $B$, which is a subset of $S$.

This follows from the rule of product, because there are 3 possibilities for each element.

share|improve this answer
add comment

Let $X$, $Y$, and $Z$ be pairwise disjoint subsets of $S$ whose union is $S$. Set $A=X$, $B=X\cup Y$. Then the pair $(A,B)$ has the right property, except that if $B=A$ then $A$ is not a proper subset of $B$.

Conversely, any pair $(A,B)$ such that $A$ is a subset of $B$ uniquely determines a partition of $S$ into pairwise disjoint subsets $X$, $Y$, and $Z$ by the rule $X=A$, $Y=B\setminus A$, and $Z$ equal to the rest.

We first count the number of ways to partition $S$ into three pairwise disjoint subsets. This is just the number of functions from $S$ to the set $\{1,2,3\}$. So there are $3^n$ ways to do the partioning

Now we throw away the number of "bad" partitions where $Y=\emptyset$. This is just the number of ways to divide $S$ into $2$ sets. There are $2^n$ ways to do that.

share|improve this answer
add comment

When you find sets $A$ and $B$ such that $A\subsetneqq B\subseteq S$, you’re really dividing $S$ into three parts: things that are in $A$ (and of course also in $B$), things that are in $B$ but not $A$, and things that are not in $B$. In other words, evern element of $S$ belongs to exactly one of the sets $A$, $B\setminus A$, and $S\setminus B$. Conversely, if you divide $S$ into parts $X,Y$, and $Z$, you can let $A=X$ and $B=X\cup Y$ to get a pair of subsets $A$ and $B$ of $S$ such that $A\subseteq B$.

There’s nothing in the statement of the problem that prevents $A$ from being empty, so there’s no harm in letting $X=\varnothing$. There’s nothing that prevents $B$ from being all of $S$, so there’s no harm in letting $Z=\varnothing$. But we’re told that $A\subsetneqq B$, so $B\setminus A\ne\varnothing$. Thus, we must ensure that the part $Y$ of our $3$-way split of $S$ gets at least one member.

In order to build such a division of $S$ into $3$ parts, you can go through $S$ one element at a time, assigning each element in turn to $X$, $Y$, or $Z$. That’s a sequence of $n$ $3$-way choices, so by the multiplication principle it can be made in $3^n$ different ways. That is, there are $3^n$ ways to divide up $S$ into the $3$ parts $X$, $Y$, and $Z$, from which, as noted above, we get $A$ and $B$ by setting $A=X$ and $B=X\cup Y$.

However, that calculation failed to take into account the requirement that $Y$ be non-empty. How many of these unwanted divisions are there? They are essentially just divisions of $S$ into two parts, $X$ and $Z$, and the same reasoning that we used in the previous paragraph shows that there must be $2^n$ of them. Subtracting them, we find that there are $3^n-2^n$ divisions of $S$ into $3$ parts $X,Y$, and $Z$ with $Y\ne\varnothing$, so that when we set $A=X$ and $B=X\cup Y$, $A$ really is a proper subset of $B$.

share|improve this answer
add comment

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.