Power set of a set contains 2^n elements.
Say S = {1,2,3}
p(S) = {phi, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3})
phi will have a null set intersection with every other element and itself, ie for phi : 2^n such intersections.
Next we pick 'one' element (say {1}). It will intersect with phi, {2}, {3}, {2,3}, i.e. it can be stated as :
1+ n-1C1 + n-1C2 +....+n-1Cn-1 , i.e. we keep on picking elements from set other than the element we are dealing with .
This gives us 2^(n-1). Now there are nC1 such possibilities(i.e. for every 'one' element). Hence total : 2^(n-1)*nC1
Similarly if we pick two elements using same logic and calculation we get : 2^(n-2)*nC2
And it goes on till n elements, i.e. {1,2,3} for 3 elements which has only one intersection with phi : 2^(n-n)*nCn = 1
So summing up it is : 2^n + 2^(n-1)*nC1 + 2^(n-2)*nC2 +......+2^(n-n)*nCn
In ordered pairs (a,b) is different from (b,a), hence we have to take both except (phi,phi),i.e. when a=b.