The Postman's Job

Apply derangement formula; [1/0!-1/1!+1/2!-1/3!+1/4!-1/5!]=44

So lets first solve this for a smaller number.Lets say 3. We will go step by step.

1. What is the total no. of ways 3 letters can be posted to 3 addresses: 3!

2. Now it includes all the ways in which only 1 letter reaches correct address. We need to remove those arrangements. If we fix 1st letter as correct the possible arrangements for rest will be: 2!. And what are the number of ways to choose a letter which reaches correct address: 3C1.

3.But we can clearly see in the above arrangement that we have included those arrangements twice in which 2 letters reach the correct address.For example when we assumed letter 1 reaching correct and when letter 2 reaching correct. So we need to add back the cases in which 2 letters reach the correct address.

Now how to do it.Number of ways to select 2 letters which reach correct address = 3C2. Number of ways remaining letters can be posted = (3-2)! i.e. 1!

4.If we apply similar logic as above we see that we included those cases where 3 letters reach the correct address. We need to subtract those cases. But first lets check how many times actually we included and subtracted the 3 letters reaching correct address.

In step 1 (When considering all cases ): included 1 time In step 2 (1 letter reaching correct address): subtracted 3 times In step 3 (2 letter reaching correct address): added back 3 times

Thus we need to subtract it once. So the number of ways this can be done is: 3C3*(3-3)! which is very logical i..e there is only 1 way that all letters reach to correct address.

If you watch closely this forms a kind of series. We are once including and then excluding.Lets see it by calculating sum: 3! - 3C1 2! + 3C2 1! - 3C3*0! = 6 -6 + 3 -1 = 2

Now lets apply this for 5: 5! - 5C1* 4! + 5C2* 3! - 5C3* 2! + 5C4* 1! - 5C5* 0! = 120-120+60-20+5-1 =44