Word-Problem on Forbidden Position Permutations (Derangement)

409 Views Asked by At

Problem
On the way into a party everyone checks a coat and a bag at the door.
On the way out , the attendant hands out coats and bags randomly.
In how many ways can this be done if "One may get one's own coat, or bag, but not both."?

My Answer $$\boxed{\sum\limits_{k=1}^{n+1} \left[ \binom{n}{k-1} D_{n-k+1}\cdot \left(\sum\limits_{i=0}^{k-1} (n-i)!(-1)^i\binom{k-1} {i}\right)\right]}$$ where $\binom{n}{r}$ denotes Binomial Coefficient. $D_n$ denotes the number of ways to derange $n$ objects

Is my answer correct$?$ And also can it be simplified further$?$

1

There are 1 best solutions below

3
On BEST ANSWER

I'm sure there are many different ways to express the result. I do not follow your logic to reach the answer appearing in the image, but here instead is my logic and solution.

Answer the related question of "In how many ways can the coats and bags be returned such that at least one person gets both their coat and bag back"

Let $A_i$ denote the event that person $i$ gets both their coat and their bag back.

We try to count $\left|\bigcup\limits_{i=1}^n A_i\right|$.

By inclusion exclusion and symmetry: $\left|\bigcup\limits_{i=1}^n A_i\right| = \sum\limits_{i=1}^n (-1)^{i+1}\binom{n}{i}\left|\bigcap\limits_{k=1}^i A_k\right|= \sum\limits_{i=1}^n (-1)^{i+1}\binom{n}{i}((n-i)!)^2$

Why is $\left|\bigcap\limits_{k=1}^i A_k\right|=((n-i)!)^2$? If the first $i$ people all get their coat and bag back, then those are already known in the arrangement. What is unknown is who among the remaining $n-i$ people received what coat and also who among the remaining $n-i$ people received what bag. There are $(n-i)!$ ways to distribute the remaining coats and then another $(n-i)!$ ways to distribute the remaining bags remembering that we could care less if any of the remaining $n-i$ people happened to get their coat or bag or both or neither. Applying multiplication principle gives the result.

Nobody getting both their coat and bag back is then the complementary event:
$$(n!)^2 - \sum\limits_{i=1}^n (-1)^{i+1}\binom{n}{i}((n-i)!)^2$$