Combinatorics Task with dwarfs

Question

There are 7 dwarfs working in a mine: D1, D2,..., D7. There are 7 tasks to do in a mine: T1, T2,..., T7. Each dwarf can do only one task. Dwarf D1 won't do task T1, dwarf D4 won't do task T2, dwarf D5 won't do task T6, dwarf D6 won't do tasks T3 and T7. Count the number of ways to distribute Tasks to Dwarfs.

Well this is how I tried counting. For T1 I can pick one of 6 dwarfs (D1 can't do it). For T2 I can pick one of 6 dwarfs (if D4 was picked to do T1 previously) or one of 5 dwarfs (if some other dwarf was picked for T1 + D4 can't do it). and so on... so the result would start like: 6 * 6 + 6 * 5 for only 2 tasks... there are a lot of combinations for all of them together.

Answer 1

The problem can be solved using rook polynomials using a board with three $1\times 1$ and one $1\times 2$ disjunct forbidden subboards.

The three $1\times 1$ subboards each have rook polynomial $1+x$ and the $1\times 2$ subboard had rook polynomial $1+2x$ and, since they are all disjunct we can multiply to get the rook polynomial $R(x)$ for the entire forbidden subboard:

$$R(x)=(1+x)^3(1+2x)=1+5x+9x^2+7x^3+2x^4$$

then the desired count is given by the substitution $x^k=(-1)^k(7-k)!$ in $R(x)$ above:

$$7!-5\cdot 6!+9\cdot 5! -7\cdot 4!+2\cdot 3!=2364\tag{Answer}$$

This can be checked using the rook polynomial solver with the following board for which Dwarfs are numbered and jobs are A to G.

Forbidden task assignments (black squares) comprise the forbidden subboard for which we have the rook polynomial $R(x)$ above.

I highly recommend rook polynomials for this kind of question, there is plenty of material available online to explain them in more detail.

Answer 2

For a direct count you need to condition on what one dwarf does to figure out the rest. It usually helps to start with the most restricted ones, so start with D6. He has five choices, two of which are distinct from the ones that somebody else won't do and three of which are the same as the one somebody else won't do. If he does one that somebody else won't do, three choices, say T1 then D1 is released. Then ask what D5 does. He can either do T2 or not. If D5 does T2 you have no further restrictions, so there are $3 \cdot 1 \5!=360$ like this. If D5 does something besides T2 then D4 has four choices and you have $3 \cdot 4 \cdot 4!=288$ like this. Now consider the cases where D6 does something nobody else cares about. Yes, it is a fair mess.

The other choice is inclusion-exclusion. Start with all $7!=5040$ ways to distribute the tasks. Subtract the $6!$ that have D1 doing T1, and each other forbidden assignment. You have subtracted the ones where two dwarves are badly assigned twice, so add them back in. Now the ones where three dwarves object have been subtracted three times and added three times, so subtract them again. Now the ones where four are unhappy... Again a bit of a mess. Take your pick.