Question

Find the rook polynomial and give an expression for the number of matchings of 5 men (rows) with 5 women (columns) given the following forbidden pairings: (M1,W2), (M1,W5), (M2,W1), (M2,W4), (M4,W3), (M4,W4), (M5, W2), (M5,W5).

Answer 1

ANSWER:

Given that,

The 5x5 board will look like this:

exchange the rows and the columns so that all we can divide the board into 2 disjoint sub boards. Each sub board will have no forbidden pairings in the same row and column,

=>For B₁, we see that it is a 2x2 square. So, we have:

r₀(B₁) = 1 (there is one way of placing 0 rooks in that square).

r₁(B₁) = 4 (there are four ways of placing 1 rook in that square).

r₂(B₁) = 2 (there are two ways of placing 2 rooks in that square).

We cannot place more than 2 rooks. So, the rook polynomial for B₁ = R(x, B₁) = 1 + 4x + 2x²

similarly,

=>For B₂, we have:

r₀(B₂) = 1 (there is one way of placing 0 rooks in that shape).

r₁(B₂) = 4 (there are four ways of placing 1 rook in that shape).

r₂(B₂) = 3 (there are three ways of placing 2 rooks in that shape).

We cannot place more than 2 rooks. So, the rook polynomial for B₂ = R(x, B₂) = 1 + 4x + 3x²

So, the rook polynomial for the forbidden squares will be the product of the two.

R(x, B) = R(x, B₁) * R(x, B₂)

= (1 + 4x + 2x²) * (1 + 4x + 3x²) = 1 + 8x + 21x² + 20x³ + 6x⁴

We now use a theorem from the inclusion-exclusion principle to assign 5 men with 5 women. =>The theorem states that the number of ways to arrange 5 pairings when there are forbidden pairings is

So, the number of possible matching of 5 men and 5 women is 20.