39this was one of user`s doubt, i thought i would pozt general method os solving it.
find no. of ways in which 4 letters can be put into 4 envelopes such dat nothin occupies its original place..............
-
UP 0 DOWN 0 1 16
16 Answers
3939number of ways in whici n letters can be placed in n directed envolopes so that no letter goes into its own envelope is
n! [ 1/2!-1/3! +1/4!-1/5!..........+(-1)n1/n!]
39here n=4 is tha case, so substitute n=4.
now dont say i am a formula mugger, this is quite a general one and have learnt after solving many such problems. and ya its not always given as letters, so relate with the question and u can find use of this formula in other cases also.
62hmm.. interesting that this has come up..
Can someone give a step by step complete logical proof to this formula?
When I mean logical, i mean it should not use any "formulas" ....
Assume that the person who has to understand does not know or even heard "Inclusion Exclusion" Principle!
Bhargav.. I am sure u can pull this off :)
39BHAIYAN, THIS IS A DIRECT RESULT FROM
PIE:principle of inclusion and exclusion
62hmm.. i know that it is a result..
but I have 2 Rules of Studying Probability Combination and Probability.. which I have said a couple of times before...
Rule 1: Dont learn Anything
Rule 2: Dont forget Rule 1
:)
;)
39A1,A2,A3,A4,.........Am are sets and A=A1UA2UA3U...UAm
n(A) = n(A1)+ n(A2) +n(A3)+.......... n(Am)
- Σn(Ai∩Aj) , 1≤i<j≤m
+Σn(Ai∩Aj∩Ak) , 1≤i<j<k≤m
and so on.......
This is called PIE
39ABOVE ALL A1,A2,A3......Am are finite sets, forgot to mention that.
62isnt this inclusion exclusion principle written in a different manner :D
3MY APPROACH TO THIS PROBLEM WAS AS BELOW PLS POINT OUT ERROR: TOTAL NO. OF WAYS . = 4! ........
NOW LET SETS A BE NO. OF WAYS IN WHICH LETTER 1 GOES TO RITE PLACCE ..B FOR LETTER 2 .....
AND SO ON TILL D ...........
NOW I FOUND n(A U B U C U D) = n(A) + n(B)...+n(D) - n(A∩B).......+n(A∩B∩C)......-n(A∩B∩C∩D) ...................
THEN I DID 4! - n(A U B U C U D) as we dont want anything goin to rite place........
but my answer is not correct explain the flaw in mah method [2][2]
{edited}
39now, we can see
if A1,A2,A3............Am are subsets of AA containing N elements, then
n(A1`∩A2`∩...........∩Am`)
= N - Σ n(Ai) +Σ n(Ai∩Aj) - Σ n(Ai∩Aj∩Ak)+......
i 1≤i<j≤m 1≤i<j<k≤m
there kindly note that in the formula i bolded, i have used compliments of A1,A2,A3..........
62where did this 5! come from...
It should be 4! na....!! or am i sleeping :P
Other than that I think that your answer is correct!
3oh!! ya 4! im soooo sorry ,..... that was dumb... now mah answer is correct!!!!!!!