N is the number of ordered pairs of nonempty sets P and Q that have the following properties:
 P ⋃ Q ={1,2,3,4,5,6,7,8,9,10,11,12}, and:
 P ⋂ Q = Φ, and:
 The number of elements of P is not an element of P, and:
 The number of elements of Q is not an element of Q
Find N.
assume that one of P,Q is empty,
then the other set has 12 elements and also has the number 12, thus violating either requirements 3 or 4.
So assume P has k elements 1<=k<=11 and thus Q has 12k elements
now if k=6 then P=Q=6 and thus 6 can not be a member of P or Q but it has to belong to one of them, thus k is not 6
now for any given k, we have that the element k must belong to Q and 12k must belong to P. That gives us k1 remaining elements to assign to set P. We have 10 remaining elements to choose these k1 from, thus this can be done in 10C(k1) ways and the remaining elements go to Q.
So the total number of combinations is
Sum(10C(k1), k=1 to 11)10C5
changing index we get
Sum(10Ck,k=0 to 10)10C5
2^1010C5
1024252=772
Thus there are 772 such ordered pairs

Posted by Daniel
on 20150413 13:46:10 