Logo
Published on

The Committee Problem with Overlapping Restrictions

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

A committee of 5 people is to be chosen from a group of 6 men and 7 women.

  1. How many different committees can be formed?
  2. How many of these committees contain exactly 2 men and 3 women?
  3. Two particular people in the group, one man (Alice) and one woman (Bob), refuse to serve on the same committee together. Given this restriction, how many valid committees of 5 people can be formed from the group of 13 people?

Hints

  • For the first part, you are choosing 5 people from a total of 6+7=136+7=13 people with no restrictions. Use combinations, not permutations, since the order of people on a committee doesn't matter.
  • For the second part, treat the selection of men and women as two separate events and multiply their combinations together.
  • For the third part, it's often easier to find the total number of unrestricted committees and subtract the number of committees where the restricted condition (Alice and Bob are both on the committee) occurs.
  • If Alice and Bob are both on the committee, how many more people do you need to choose, and from how many remaining people?

Solutions

  1. We need to choose 5 people from a total group of 13 (6+76+7). The number of ways to do this is: (135)=13!5!×8!=13×12×11×10×95×4×3×2×1=1287\binom{13}{5} = \frac{13!}{5! \times 8!} = \frac{13 \times 12 \times 11 \times 10 \times 9}{5 \times 4 \times 3 \times 2 \times 1} = 1287 So, there are 1287 possible committees.

  2. To form a committee with exactly 2 men and 3 women, we choose 2 men from the 6 available, and 3 women from the 7 available. Number of ways = (62)×(73)\binom{6}{2} \times \binom{7}{3} (62)=6×52×1=15\binom{6}{2} = \frac{6 \times 5}{2 \times 1} = 15 (73)=7×6×53×2×1=35\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 Total ways = 15×35=52515 \times 35 = 525.

  3. Let's use the complementary counting method. Total number of unrestricted committees = 1287. Now, let's find the number of "bad" committees where both Alice (man) and Bob (woman) are chosen. If Alice and Bob are both on the committee, we have already chosen 2 members. We need to choose 5−2=35 - 2 = 3 more members to complete the committee. These 3 remaining members must be chosen from the remaining 13−2=1113 - 2 = 11 people. Number of "bad" committees = (113)=11×10×93×2×1=165\binom{11}{3} = \frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 165.

    The number of valid committees is the total minus the "bad" committees: Valid Committees=1287−165=1122\text{Valid Committees} = 1287 - 165 = 1122

    Alternatively, we can use direct counting (Inclusion-Exclusion): Ways with Alice but not Bob: Alice is chosen (1 way), Bob is excluded. We choose 4 more from the remaining 11 people. (114)=330\binom{11}{4} = 330. Ways with Bob but not Alice: Bob is chosen, Alice is excluded. We choose 4 more from the remaining 11 people. (114)=330\binom{11}{4} = 330. Ways with neither Alice nor Bob: We choose 5 from the remaining 11 people. (115)=462\binom{11}{5} = 462. Total valid ways = 330+330+462=1122330 + 330 + 462 = 1122. Both methods yield the same correct result!


Takeaways

  • Complementary counting (Total - Unwanted = Wanted) is often the fastest method when dealing with "at least one" or "refuse to be together" restrictions.
  • Always clearly identify whether a problem is a permutation (order matters) or a combination (order does not matter). Committees are almost exclusively combinations.
  • Direct counting (breaking down into mutually exclusive cases) is a fantastic way to double-check your answer in an exam scenario if time permits.

Further Readings


Connect with me

Counting problems can be tricky, but practicing different approaches builds confidence!