$7$ dwarfs $d_1, ... , d_7$ have $7$ jobs $j_1, ... , j_7$ to do every day

Question

$7$ dwarfs $d_1, ... , d_7$ have $7$ jobs $j_1, ... , j_7$ to do every day.
But: $$d_1 \text{ can't do } j_2, j_3$$ $$d_2 \text{ can't do } j_1, j_5$$ $$d_4 \text{ can't do } j_2, j_7$$ $$d_5 \text{ can't do } j_4$$ How many ways can they separate their work differently each day?

In this task we know that every dwarf can only do $j_6$. $j_1,j_3,j_4,j_5,j_7$ can be done by $6$ dwarfs. And $j_2$ can be done by $5$ dwarfs.

However this observation is not enough to finish this task. I need an intelligent way to connect this fact with a sollution.

Can you help me?

Answer 1

Another way to look at the problem is that it is the number of ways to place seven non-attacking rooks on the following 7 by 7 board, where an $X$ denotes a forbidden square.

"Non-attacking" means that no two rooks may be placed in the same row or column.
We can solve this problem by finding the rook polynomial of the forbidden sub-board, followed by an application of the principle of inclusion / exclusion. The rook polynomial $R(x)$ of a board is by definition a polynomial whose coefficient of $x^n$ is the number of ways to place $n$ non-attacking rooks on the board. We define the number of ways to place zero rooks as $1$. Two sources for additional information about rook polynomials are An Introduction to Combinatorial Analysis by John Riordan and Schaum's Outline of Theory and Problems of Combinatorics by V.K. Balakrishnan.

It's clear we can delete any unused rows or columns without changing its rook polynomial. With that modification, our board becomes $$\begin{bmatrix} &X & & \\ X & &X & \\ X & & & \\ & & &X \\ &X & & \\ & &X & \\ \end{bmatrix}$$ where we have switched to a matrix representation and marked forbidden squares with an $X$. We adopt the convention that such a matrix is interchangeable with the rook polynomial of the marked squares, so for example we may write $$\begin{bmatrix} X \end{bmatrix} = 1 + x$$ because the rook polynomial of a single-square board $\begin{bmatrix} X \end{bmatrix}$ is $1+x$.

Some properties of rook polynomials that we will use are:

• Permuting the rows or columns of a board does not change its rook polynomial.
• Any row or column without an $X$ in it can be deleted without altering the rook polynomial.
• If the board can be divided into two sub-boards which do not share an $X$ in the same row or column, then the rook polynomial is the product of the rook polynomials of the sub-boards. For example, $$\begin{bmatrix} X & & \\ &X &X \\ &X &X \end{bmatrix} = \begin{bmatrix} X \end{bmatrix} \cdot \begin{bmatrix} X &X \\ X &X \end{bmatrix}$$ (It may take some thought to convince yourself of the truth of this last statement.)

To evaluate the rook polynomial of our chosen board, we designate one square, marked with a box, and we divide the possible arrangements of rooks into two cases: those in which a rook is placed on the designated square and those in which it is not. $$\begin{bmatrix} &X & & \\ X & &\boxed{X} & \\ X & & & \\ & & &X \\ &X & & \\ & &X & \\ \end{bmatrix}$$ If $R(x)$ is the rook polynomial of the total board, then since all arrangements fall into one of those two cases, $R(x) = S(x) + x T(x)$, where $S(x)$ is the rook polynomial of the board with the row and column of the designated square deleted, and $T(x)$ is the rook polynomial ot the board with only the designated square deleted. The $x$ in front of $T(x)$ accounts for the rook on the deleted square. Then $$ S(x) = \begin{bmatrix} &X & \\ X & & \\ & &X \\ &X & \\ \end{bmatrix} = \begin{bmatrix}X \end{bmatrix} \begin{bmatrix} X\\ X \end{bmatrix} \begin{bmatrix}X \end{bmatrix} = (1+2x) (1+x)^2 $$ and $$ T(x) = \begin{bmatrix} &X & & \\ X & & & \\ X & & & \\ & & &X \\ &X & & \\ & &X & \\ \end{bmatrix} = \begin{bmatrix} X\\ X \end{bmatrix} \begin{bmatrix} X\\ X \end{bmatrix} \begin{bmatrix}X \end{bmatrix} \begin{bmatrix}X \end{bmatrix} = (1+2x)^2 (1+x)^2 $$ so $$R(x) = x S(x) + T(x) = 1 + 7x + 17x^2 +17x^3 +6x^4$$

By Inclusion / Exclusion, the number of ways to place seven non-attaching rooks on the $7$ by $7$ board with none on the forbidden sub-board is $$1 \times 7! - 7 \times 6! + 17 \times 5! - 17 \times 4! + 6 \times 3! = \boxed{1668}$$

Answer 2

Create a matrix where $M_{i,j}=1$ if dwarf $i$ can do job $j$ and $0$ otherwise.

$$\left[\begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{array}\right] $$ Consider the bipartite graph whose adjacency matrix is $M$. A complete job assignment corresponds to a perfect matching in that graph. This count can be accomplished by calculating the permanent of this matrix, which is similar to the determinant except that all of the permutations are added. According to an online calculator, there are a total of 1668 complete job assignments.

Answer 3

Finding a complete matching in bipartite graphs (or alternatively, proving that none exists) can be accomplished by polynomial time algorithms. Once we have one such complete matching, they can all be enumerated with an algorithm proposed by Takeaki Uno with complexity $O(n)$ per matching.

The history of complete bipartite matching algorithms is itself interesting. See the Hungarian algorithm in Wikipedia, which explains the developments:

In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

As formulated by Kuhn (1955) and analyzed by Munkres (1957), the algorithm has complexity $O(n^4)$. However Edmonds and Karp (and independently Tomizawa) saw that with a slight modification one can achieve $O(n^3)$ complexity.

As a general outline one can begin by finding a maximal matching, i.e. match as many vertices as possible until no further edges can be added. One then searches systematically for augmenting paths, success at which increases the count of matched vertices (equiv. the number of edges in the matching). In this way we find either a complete bipartite matching or show that none exists.

The topic comes up often at sister sites StackOverflow (e.g. Augmenting Path - Maximum Matching) and CS.SE (e.g. Perfect matching in a graph and complete matching in a bipartite graph).

Answer 4

One (theoretically) simple way to do this is via using generating functions:

We take $j_1,...,j_7$ as free algebraic elements. Then we create for each dwarf a generating function in these elements, so that each dwarf has as generating function the sum of exactly those jobs he can do.

E.g.: $$ d_1 = j_1+j_4+j_5+j_6+j_7$$ $$ d_2 = j_2+j_3+j_4+j_6+j_7$$

If we now multiply $\prod_{i=1}^7 d_i$ and extract the coefficient of $j_1j_2j_3j_4j_5j_6j_7$, then this is exactly the possible ways to split the jobs.