Number of subset pairs

by hemangsarkar, Jun 20, 2016, 7:10 AM

Q) Let A be a set of the first N positive integers :A={1,2,3,4.........N}.
Let B be the set containing all the subsets of A.
A relations is defined as follows:

R1={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is equal to empty set }

NOTE : (x,y) is the same as (y,x) ,i.e the pairs are unordered.

example:
Let A={1,2}
Then B={Phi,{1},{2},{1,2}}
Phi=Empty Set
So R1=Either {({1},{2})} or {({2},{1})} hence number of relations is 1.

Solution:

We are given a number $n$ , the first thing we need to think of is how many numbers from $1$ to $n$ can we use to make our relation? We can use a minimum of $2$ numbers and a maximum $n$ numbers.

Let us use say $p$ numbers where $2 \leq p \leq n$ .

Number of ways to select $p$ numbers out of $n$ numbers is $\binom{n}{p}$ .

Once we have selected $p$ numbers, we start thinking about our unordered pair $(x,y)$ .

$x$ can contain a minimum of $1$ and a maximum of $p-1$ numbers. Hence if we are considering ordered pairs then we can have a total of

$\binom{p}{1} + \binom{p}{2} + \binom{p}{3} + \cdots + \binom{p}{p-1}$

pairs.

We know that $\binom{p}{0} + \binom{p}{1} + \binom{p}{2} + \cdots + \binom{p}{p} = 2^{p}$ .

hence our required sum is $2^{p} - 2$ .

But this counts the number of ordered pairs and we want number of unordered pairs hence we divide by $2$ .

$2^{p-1} - 1$ pairs for $p$ numbers selected out of $n$ numbers.

We can easily see that the final answer will be:

$\sum_{p=2}^{n} \binom{n}{p}(2^{p-1} - 1)$

or, $\sum_{p=2}^{n} \binom{n}{p}2^{p-1} - \sum_{p=2}^{n} \binom{n}{p}$

or, $\left(\frac{1}{2}\right)\left(\sum_{p=0}^{n} \binom{n}{p}2^{p} -1 - 2n\right) - 2^{n} + 1 + n$

or, $\left(\frac{1}{2}\right)\left(\sum_{p=0}^{n} \binom{n}{p}2^{p} +1\right) - 2^{n}$

or, $\left(\frac{3^{n} + 1}{2}\right) - 2^{n}$

You can also go here to see another solution:
http://math.stackexchange.com/questions/216984/finding-the-number-of-subset-pairs-of-a-set

This post has been edited 2 times. Last edited by hemangsarkar, Jun 20, 2016, 8:05 AM

Comment

hemangsarkar's blog

Number of subset pairs

by hemangsarkar, Jun 20, 2016, 7:10 AM

0 Comments