2
$\begingroup$

Two letters need to be delivered to each of n houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter?


I got stuck and don't now how to progress. Can someone provide hint?

1) $(2n)!/2^n$ is the number of all possible onto functions from our domain of houses to the codomain of letters.

2) Let $A_i$ be property that two delivered letters are correct. $ |A_1' \cup A_2' \cup... \cup A_n'|=(2n)!/2^n-|A_1 \cap A_2 \cap... \cap A_n|$ I tried everything I could come up with but I cannot find $|A_1 \cap A_2 \cap... \cap A_n|$. I feel like I need to find union first but in order to do that I should find intersection. Really confused. Any hint would be appreciated.

Edit: Corrected mistake in the equation.

$\endgroup$
  • $\begingroup$ Your equation in 2 is not correct. The left side is what you want-the number of ways to have all the letters are incorrect. The intersection on the right is the chance that all the letters are correct. To use this approach, you would have to consider the chance that some are correct and some not. $\endgroup$ – Ross Millikan Nov 19 '14 at 18:51
  • $\begingroup$ |A1∩A2∩...∩An| this is the last term in the Inclusion Exclusion formula for |A1∪A2∪...∪An|, but in order to find it unit to find |A1∪A2∪...∪An| which can be found if we know |A1∩A2∩...∩An|. That is what I'm stuck at; I don't see how it is possible. $\endgroup$ – Basil M. Nov 19 '14 at 19:14
  • $\begingroup$ Yes, it is the last term in inclusion/exclusion, but there are many more to add and subtract. I don't see a way to get there reasonably. $\endgroup$ – Ross Millikan Nov 19 '14 at 19:20
1
$\begingroup$

Let $D_n=(2n)!/2^n$ denote the number of all possible ways to deliver the letters, and let $\Delta_n$ denote the number of ways to deliver them so that each house gets at least one wrong letter. Inclusion-exclusion says

$$\Delta_n=D_n-{n\choose1}D_{n-1}+{n\choose2}D_{n-2}-{n\choose3}D_{n-3}+\cdots+(-1)^nD_0$$

The sequence for $D_n$, starting at $n=0$, is $1,1,6,90,2520,\ldots$. I get the corresponding sequence for $\Delta_n$, starting at $n=1$, to be $0,5,74,2193,\ldots$. E.g.,

$$\Delta_4=2520-4\cdot90+6\cdot6-4\cdot1+1=2520-360+36-4+1=2193$$

This sequence doesn't appear in the OEIS. That doesn't automatically prove anything, but it suggests the answer is unknown. So good luck!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.