Seven jobs processed on Seven machines. Each machine process only job and all jobs must be processed. How many assignments are possible?

167 Views Asked by At

enter image description here

Ignoring Column #1, Column #7, Row #2, Row #7, we can complete the rook polynomial for the smaller board (Since machine 1 has to process job 2, and machine 7 has to process job 7). This gives us the rook polynomial of

$R(x,B) = 1 + 4x + 6x^2 + 4x^3 + x^4$

If we let $A_i$ be that a machine is assigned to the shaded area, by principle of inclusion-exclusion we can arrive to the following:

$7! - (6!4 - 5!6 + 4!4 - 3!1)$

Would this be the right approach to the problem?

1

There are 1 best solutions below

0
On BEST ANSWER

You have the right basic approach, but you’ve not carried it out correctly. After you remove rows $2$ and $7$ and columns $1$ and $7$, you have this board, where I’ve numbered the forbidden squares:

$$\begin{array}{|c|c|c|} \hline &&&&\;\;\\ \hline &&&4&\\ \hline &&3&&\\ \hline &2&&&\\ \hline 1&&&&\\ \hline \end{array}$$

The deleted rows and columns do not contribute anything, since the assigments there are fixed.

The rook polynomial for the forbidden sub-board is $(1+x)^4=1+4x+6x^2+4x^3+x^4$. If $A_k$ is the set of placements of $5$ rooks on this board that have a rook on cell $k$ (for $k=1,\ldots,4$), then an inclusion-exclusion calculation shows that the number of ‘bad’ job-machine assignments is

$$\begin{align*} \left|\bigcup_{k=1}^4A_k\right|&=\sum_{\varnothing\ne I\subseteq[4]}(-1)^{|I|-1}\left|\bigcap_{k\in I}A_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[4]}(-1)^{|I|-1}(5-|I|)!\\ &=\sum_{i=1}^4\binom4i(-1)^{i-1}(5-i)!\;. \end{align*}$$

The number of acceptable assignments is therefore

$$\begin{align*} 5!-\sum_{i=1}^4\binom4i(-1)^{i-1}(5-i)!&=5!+\sum_{i=1}^4\binom4i(-1)^i(5-i)!\\ &=\sum_{i=0}^4\binom4i(-1)^i(5-i)!\\ &=5!-4\cdot4!+6\cdot3!-4\cdot2!+1\cdot1!\\ &=53\;. \end{align*}$$

In the language of rook placements, we really are placing only $5$ rooks, not $7$, because $2$ of the original $7$ have forced placements and so contribute no variety.