# Permutation Question help

1. Jun 17, 2013

### kashan123999

1. The problem statement, all variables and given/known data

A notorious postman delivered 4 letters to four houses in such a way that no house will get the correct letter.....in how many ways he delivered the letter ? Please explain it

2. Relevant equations

I think this is permutation question...using fundamental law of counting

3. The attempt at a solution

I dont know where to start,i think they can be delivered in 7 ways cause first letter will be delivered in 3 ways,because 1 house is correct..after that 2nd letter can be arranged in 2 ways...3rd and 4th in 1 1 way..so 3+2+1+1=7 ways....

2. Jun 17, 2013

### Fredrik

Staff Emeritus
Are you sure you're supposed to be adding those numbers?

3. Jun 17, 2013

### CAF123

The first letter can be delivered to the first house in 3 ways, as you noted. However depending on what this letter is, there may or may not be 2 choices for the second house. For example, denote the four houses by A,B,C,D and their correct letters by a,b,c,d. If we have b going to house A, then we have 3 choices for the letter in B. While if we have,say, c in A, then we can only have two choices for B(a and d).

4. Jun 17, 2013

### Fredrik

Staff Emeritus
Ah, I didn't notice that. Here's a slightly different way of looking at it. Let's say that he delivers the letters a,b,c,d in alphabetical order. There are 3 houses where he can leave a. If he leaves a at B, there are now 3 houses where he can leave b. But if he leaves a at C or D, there are now only 2 houses where he can leave b.

5. Jun 17, 2013

### lurflurf

There are only 24 permutations, it might be instructive to write them all out. Another approach is to consider that there are three choices for the first slot (ie 2,3,4 not one), one can go any where else (ie slot 2,3,4 not one) but where ever 1 goes determines where the other numbers go. So each choice is a choice of what slot one goes in and what goes in slot one so it is easy to see the possibilities.

Last edited: Jun 17, 2013
6. Jun 17, 2013

### kashan123999

7. Jun 17, 2013

### Ray Vickson

Forum rules require you to work that out for yourself. You have received several hints, and that should be sufficient.

8. Jun 17, 2013

As lurflurf said , write all the choices. It might take some time but it is a good way to understand problems like this.

9. Jun 17, 2013

### TimeToShine

How about you try and find the probability that the postman does deliver to the right house? This should be basic enough. Subtract your answer from 1, and use this to compare to your answer using permutations.

10. Jun 17, 2013

### Ray Vickson

That won't work: he wants the number of permutations in which every element is in the wrong place, but your method will get him the number in which at least one (hence at least two) are in the wrong place. The OP wants to find the number if derangements, although he may not know that.

11. Jun 18, 2013

### lurflurf

!4
done!
Why didn't we do that sooner?
We can do {delivers all to wrong houses}={all}-{delivers to the right house)
delivers to the right house in this case means at least one letter.
As you point out we cannot have 3 right
so we have
{0 right}={all}-{4 right}-{2 right}-{1 right}

Summary of Methods suggested
A)
pick one slot ie 1
choose which what to put there (in 1)
chose where to put what was there before (where 1 goes)
B)
!4
done!
C)
{0 right}={all}-{4 right}-{2 right}-{1 right}
D)
Enumerate (write out or draw) all possibilities

Last edited: Jun 18, 2013