Day 24: Deranged Distribution

Let us call a permutation where all the objects are not in their original places a derangement ; define $D(n)$ as the number of derangements for $n$ objects. $D(n)$ is a well known function whose formula can be derived using the Principle of Inclusion and Exclusion .

First we consider how many ways there are to get only two presents correct. We choose two presents to be fixed then we multiply by the number of derangements of the other five objects. So there are: $\binom{7}{2}\times D(5) = 21 \times 44 = 924$ ways.

Then we consider how many ways there are for three objects correct up to seven objects correct, giving us: $924 + 315 + 70 + 21 + 0 + 1 = \boxed{1331}$ ways as our answer.

It is also possible to consider the complement using $D(7)$ and $D(6)$ , but I think that this method's calculation is perhaps easier.

Number of ways to get atleast two correct = Total - Number of ways of getting none correct - Number of ways of getting one correct.
Total number of ways to arrange = $7!$
Number of ways to get none correct = $7! \displaystyle \sum_{i=0}^{7}(-1)^{i}\dfrac{1}{i!}= 1854$ [ Using the Derangement theorem ]

Number of ways to get one right = Choosing one house which gets correctly $\times$ Derangements of other 6 = $\dbinom{7}{1} \times 6! \displaystyle \sum_{k=0}^{k=6}(-1)^{k}\dfrac{1}{k!} = 1855$
$\therefore$ Require ways $= 5040 - 1854 - 1855 = 1331$

Answer = 7! - (D7+7*D6)=1331. where Dn denotes the number of ways in which n caps can be distributed to n persons such that nobody recieves his own cap.(Google it if you want)