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

Printable View

- Jan 6th 2008, 01:07 PMvivianordered 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 PMPlato
For a particular subset and

*B*has*k*elements then there are subsets of*B*. Hence there are ordered pairs*(A,B)*where . BUT that is only for one particular subset.

Let’s do the general case: for any number*j*, , there are subsets of having*j*elements. Thus there are pairs of the form*(A,B)*where and |B|=j.

The total count: . - Jan 7th 2008, 12:00 AMOpalg
Comparing that with the binomial formula , you see that the total count is (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: (but I wouldn't have thought of that if I hadn't seen**Plato**'s answer first).