Combinatorics based on recursion

Question

The question that I came across is - There are $n$ men who have to give up their hats and coats before entering a hall, and on leaving they receive back a coat and hat randomly. We are asked to count the number of cases where no man gets back both of their hat and coat ; it is possible to get back just one of either hat or coat or maybe none of them. So, my approach to the problem has been something like -

If $n = 2$, lets say the two people are $A$ and $B$, so $\{(\text{what $A$ gets}),(\text{what $B$ gets})\}$ can be {(H_B,C_B),(H_A,C_A)} OR {(H_B,C_A),(H_A,C_B)} OR {(H_A,C_B),(H_B,C_A)} just these 3 cases possible.

If $n=3$, lets say the algorithm I am using is the third person comes and exchanges either its coat or its hat or both of it with one of the 3 combinations of $n=2$. So, for one exchange it can be in $2$ ways - so a $2\times2\times3$ ways of one exchange; for two exchange it can be in $2\times2\times3$. One more case can be if for $n=2$ they had an illegal {(H_A,C_A),(H_B,C_B)} where the illegal nature could be removed by an alternate exchange of hat from A and coat from B and vice-versa, i.e.- another $2$ more cases. So, a total of $26$ cases for $n=3$

How to proceed further for $n=4$ or in fact any general $n$? Try to keep to the basics as I am just an undergrad and use recursion in the answer if possible.

Answer 1

To avoid confusion:

Originally, I posted several comments, suggesting that the problem could be tackled through consideration of Partial Derangements and [Inclusion-Exclusion](See this article.

I have thought of an easier way (shown below). So, I deleted my comments.

---

Let $D_1, D_2$ denote the number of fixed points in the distribution of the coats and hats, respectively. Then, $D_1,D_2 \in \{0,1,2,\cdots,n\}.$

Let $f(r)$ denote the number of ways that $r$ items are completely deranged. Per this Derangements article

$$f(r) = r! \times \left[\sum_{i=0}^r \frac{(-1)^i}{i!}\right] \implies f(0) = 1. \tag1 $$

---

There are $(n+1)^2$ mutually exclusive cases to consider, for the various combinations of $D_1, D_2.$

For a specific combination of $D_1,D_2$, you can reason as follows:

There are $~\displaystyle \binom{n}{D_1}~$ ways of selecting the Coat fixed points. Since there can be no intersection among the fixed points, there are then $~\displaystyle \binom{n-D_1}{D_2}~$ ways of selecting the Hat fixed points.

So, the desired enumeration, for a specific ordered pair $(D_1, D_2)$ is

$$g(D_1,D_2) = \binom{n}{D_1} \times \binom{n-D_1}{D_2} \times f(n-D_1) \times f(n-D_2). \tag2 $$

---

Therefore, the problem has been reduced to determining the pertinent ordered pair values for $D_1, D_2$ and expressing the summation of $g(D_1,D_2)$ values accordingly.

Let $~A~$ denote :

• $~\displaystyle \frac{n}{2} ~: n~$ even.

• $~\displaystyle \frac{n-1}{2} ~: n~$ odd.

By symettrical considerations, you can examine the ordered pairs where $D_1 < D_2$ and multiply that enumeration by $(2)$.

When $D_1 < D_2,$ then $D_1$ must be $~\leq A~$ and $D_2$ must be $\leq (n - D_1)$.

When $D_1 = D_2,$ then $D_1$ must be $~\leq A~$.

Therefore, the final computation is

$$\left[ ~\sum_{j=0}^A g(j,j) ~\right] + \left\{ ~2 \times\left[ ~\sum_{j=0}^A ~\left( ~\sum_{k = j+1}^{n - j} g(j,k) ~\right) ~\right] ~\right\}. \tag3 $$

Note
In the 2nd summation in (3) above, when $n$ is even and $j = A$, then there are no integers $k$ such that $j+1 \leq k \leq n - j.$ So, in that cirumstance, there are $(0)$ terms to sum.