There are 4 women W_1, W_2, W_3, W_4 and 5 men M_1, M_2, M_3, M_4, M_5 in a group. We are required to form 4 pairs each consisting of one woman and one man. W_1 is not to be paired with M_1, and M_4 must necessarily be paired with someone. In how many ways can such 4 pairs be formed?
A. 74
B. 76
C. 78
D. 80
GATE 2017 · General Aptitude · Combinatorics · medium
Answer: 78
Case A: M_1 is the excluded man: Men available: {M_2, M_3, M_4, M_5}. Since M_1 is absent, the W_1-M_1 restriction is automatically satisfied. All 4! = 24 pairings are valid.
Case B: M_2 is excluded (M_1 is present): Men: {M_1, M_3, M_4, M_5}. Total pairings = 24. Subtract forbidden: W_1 paired with M_1 and remaining 3 women matched to 3 men = 3! = 6. Valid = 18.
Case C: M_3 is excluded (M_1 is present): Men: {M_1, M_2, M_4, M_5}. By the same logic as Case B, valid pairings = 18.
Case D: M_5 is excluded (M_1 is present): Men: {M_1, M_2, M_3, M_4}. Valid pairings = 18.
Total valid pairings: Sum over all 4 cases: 24 + 18 + 18 + 18 = 78.