Elementary combinatorics.

Question

Suppose there are six different shirts of one color and six different trousers of same colours as that of shirts. In how many ways these can be put on by five people such that no person wears the shirt and trouser of the same colour.

I knew one part of the answer as $\binom{6}{5}×5!×D_5$. But actually we can see more for example for the selection of shirts $s_1,...s_5$ the trousers selection could be $t_2,...t_6$. Could not do after this.

Answer 1

We start with all possible permutations of the 5 people wearing one of the 6 shirts and one of the 6 trousers (one permutation for shirts and one for trousers). That would be: $$ P(6,5)\cdot{P(6,5)}=6!\cdot{6!}\qquad(1) $$ Then we need to subtract all the cases where exactly one person wears same colour clothes. That would be: $$ - P(6,1)\cdot{C(5,1)}\cdot{(6-1)!}\cdot{(6-1)!}\qquad(2) $$ where:

• $C(5,1)$ are the persons wearing same colour clothes. If exactly one person, it could be person 1, or person 2, or... or person 5.
• $P(6,1)$ are the clothes that the above persons are wearing. We have 6 colours, so it could be any of the 6 colours.
• Now we are left with 4 people having to wear 5 different colours. The number of permutations (as per above) is: $P(5,4)\cdot{P(5,4)}=5!\cdot{5!}$

But we have now also subtracted cases where more than one person wears same colour. For two people wearing same colour, we subtracted these cases twice (once when considering the first person and again when considering the second person). We have the following:

• For exactly one person, we subtracted once
• For exactly two persons, we subtracted twice
• ...
• For exactly five persons, we subtracted five times

We now need to add back once the cases of exactly two persons wearing same clothes (because we subtracted twice). That would be: $$ + P(6,2)\cdot{C(5,2)}\cdot{(6-2)!}\cdot{(6-2)!}\qquad(3) $$ where:

• $C(5,2)$ are the persons wearing same colour clothes. Eg, person 1 and 2, person 1 and 3 etc.
• $P(6,2)$ are the clothes that the above persons are wearing. We have 6 colours and two persons. This is a permutation because, for example: (person 1 = red and person 2 = blue) is different than (person 1 = blue and person 2 = red).
• Now we are left with 3 people having to wear 4 different colours. The number of permutations (as per above) is: $P(4,3)\cdot{P(4,3)}=4!\cdot{4!}$

Now consider the cases where exactly 3 people wear same colour clothes. With (2) we subtracted these three times. But with (3), we added them three times. We need to subtract them once. If you continue this logic you will see that we need to alternate subtraction and addition (for exactly one person, exactly two persons, exactly three persons etc.). The final formula is: $$ \sum_{k=0}^5(-1)^k\cdot{P(6,k)}\cdot{C(5,k)}\cdot{(6-k)!}\cdot{(6-k)!}=222480 $$

Answer 2

We can just make a straightforward inclusion-exclusion calculation:

$$\sum_{k=0}^5 (-1)^k\cdot\binom{6}{k}\binom{6-k}{5-k}^2 \cdot (5-k)!=1854.$$

In this calculation $k$ is the number of people that we make to wear the same color shirt and trousers, $\binom{6}{k}$ is the number of ways to choose clothes for them, $\binom{6-k}{5-k}^2$ is the number of ways to choose clothes for the other $5-k$ people, $(5-k)!$ ways to get pairs shirt-trousers for those $5-k$ people.

Edit: If you distinguish $5$ people that receive the clothes, then the answer is exactly $P_5=5!$ times greater: $$1854\cdot 5!=222480.$$

Edit 2: Another nice reasoning just came to my mind. Let us make a row of shirts and distribute the trousers between them. There are $D_6$ ways to do so that no color is matched. We then can take any $5$ pairs of clothes. This gives $6\cdot D_6$ ways.

Now let us allow one matching. There are $6$ ways to choose which pair will match. And then there are $D_5$ ways to distribute the trousers. We can only take non-matching pairs of clothes. In total, $$6\cdot(D_5+D_6)=D_7=1854$$ ways due to the recursive formula for $D_n$. Again, if we distinguish the $5$ people, then the answer is $$P_5\cdot D_7=222480.$$