4 letters, A,B,C,D should go to 4 independent houses, 1,2,3, and 4, respectively. What's the no. of possible ways so that no letter goes to the correct address.
Please explain your answer. I am not looking for a listing approach.
This is a problem of de arrangement, where none of the things are at the correct place...
If n things are to be arranged such that none of the things are at correct place , then total possible de arrangements is given by formula
n! ( 1 - 1/1! + 1/2! -1/3! +1/4! -1/5! .....(-1)^n/n! )
When n=4,
total possible de arrangements = 4 ! ( 1 - 1/1! + 1/2! -1/3! +1/4!
= 24 ( 1-1 + 1/2 - 1/6 + 1/24 )
= 24 ((12-4+1)/24)
= 9
Alos, let us try the classical approach..
There are 4 envelopes ..say A B C D
Now, A can be at one of the 3 incorrect places I.e B, C Or D..
Let us evaluate each of the 3 possibilities :
1) When A is at B..
No of incorrect places for B = 3
No of incorrect places for C = 1
and D has to occupy last incorrect place..
total incorrect ways when A is at B = 3*1*1 = 3 ways..
Similarly, when A is at C, there would be 3 incorrect places for C, and a single incorrect place for B and D..
Hence, 3 ways..
similarly, 3 incorrect places when A is at D..
Total incorrect places = 3+3+3 = 9...this takes care of all incorrect possibilities.
Theory for the Inclusion-Exclusion principle/de arrangement can be read here:
Math Forum - Ask Dr. Math AND
http://www.physics.harvard.edu/academics/undergrad/probweek/sol16.pdf