We lost a coding contest yet again. Here's the problem:
A is a set containing 'n' elements. '
In how many ways can 3 non-empty subsets of A be chosen, such that their pairwise intersections are empty?
Note: Pairwise intersections of 3 sets P, Q, R
are : P ^ Q, Q ^ R and R ^ P.
1) 4^n
ReplyDelete2) 4^n - 3^n
hope its correct!
yup-4^n
ReplyDeleteshivankar;;2nd answer kis liye?
^ at least jo question mujhe dikh raha hai, uska ans 4^n nahi ho sakta
ReplyDeletehints:
ReplyDeleten=3: ans: 1
n=4: ans: 10
oops.. so we're wrong..
ReplyDeleteand by the way.. there ws a second question some till last night! :P
is vaale ke liye maine 4^n - 3^n likha tha.. but its wrong..
ReplyDeleteI am getting summation{from r=3 to n}[(nCr)*{3^n-r - 3*2^n-r + 3}]
ReplyDeleteI used the formula of r^n-rC1(r-1)^n + rC2(r-2)^n......
here n=no. of elements which are changing from n to 3 because rest elements would be going in none of the given set but in a superficial fourth set and that superficial set can be empty also so, it cannot be included in above formula therefore, summation is to be done from r=3 to n
summation contains nCr because we also have to include all possible cases of different elements getting excluded.
ReplyDeletebtw, a brilliant question and much more brilliant if I am wrong(should be). thank you bhaiya!
This comment has been removed by a blog administrator.
ReplyDelete4^n-3^(n+1)+3.2^n-4. if all n elements are different
ReplyDeletehell!!! koi solution to do!
ReplyDeletewhats d final answer?
ReplyDelete(4^n-3^(n+1)+3.2^n-1)/6
ReplyDeletethanks bhaiya..
ReplyDelete