# ordered pair!!

• Jan 6th 2008, 01:07 PM
vivian
ordered pair!!
Determine the number of ordered pairs (A,B), where A is a subset of B and B is a subset of {1,2,....,n}.
• Jan 6th 2008, 01:43 PM
Plato
Quote:

Originally Posted by vivian
Determine the number of ordered pairs (A,B), where A is a subset of B and B is a subset of {1,2,....,n}.

For a particular subset $\displaystyle B \subseteq \left\{ {1,2,3, \cdots ,n} \right\}$ and B has k elements then there are $\displaystyle 2^k$ subsets of B. Hence there are $\displaystyle 2^k$ ordered pairs (A,B) where $\displaystyle A \subseteq B$. BUT that is only for one particular subset.

Let’s do the general case: for any number j, $\displaystyle 1 \le j \le n$, there are $\displaystyle {n \choose j}$ subsets of $\displaystyle \left\{ {1,2,3, \cdots ,n} \right\}$ having j elements. Thus there are $\displaystyle {n \choose j}2^j$ pairs of the form (A,B) where $\displaystyle A \subseteq B$ and |B|=j.

The total count: $\displaystyle \sum\limits_{j = 0}^n {{n \choose j} 2^j }$.
• Jan 7th 2008, 12:00 AM
Opalg
Quote:

Originally Posted by Plato
The total count: $\displaystyle \sum\limits_{j = 0}^n {{n \choose j} 2^j }$.

Comparing that with the binomial formula $\displaystyle (x+y)^n = \sum\limits_{j = 0}^n {{n \choose j} x^jy^{n-j} }$, you see that the total count is $\displaystyle 3^n$ (put x=2, y=1).

You can see this answer directly from the original question if you argue as follows. For each integer from 1 to n, there are three possibilities: (a) it belongs to both A and B, (b) it belongs to B but not A, (c) it belongs to neither. Total number of possible choices: $\displaystyle 3^n$ (but I wouldn't have thought of that if I hadn't seen Plato's answer first).