the world is a theatre

Topics

• combinatorics

The problem asks us to find the number of ways to choose a group of exactly $t$ actors from $n$ boys and $m$ girls such that there are at least 4 boys and at least 1 girl in the group.

Constraints: $4\le n\le 30,1\le m\le 30,5\le t\le (n+m)$

Idea

A direct approach to solve this problem is to consider the constraints and use combinations. Let’s think about the complementary counting approach. It’s often easier to calculate the total number of ways without any restrictions and then subtract the number of invalid ways.

The total number of ways to choose a group of $t$ actors from $n$ boys and $m$ girls, without any restrictions, is simply choosing $t$ people from a total of $n+m$ people. This can be calculated using combinations as $\left(\genfrac{}{}{0ex}{}{n+m}{t}\right)$.

Now, we need to subtract the number of invalid groups, which are the groups that do not satisfy the condition “at least 4 boys and at least 1 girl”. The negation of this condition is “(less than 4 boys) OR (less than 1 girl)“. Let’s consider these invalid cases:

Case 1: The number of boys is less than 4. This means the number of boys can be 0, 1, 2, or 3.
Case 2: The number of girls is less than 1. This means the number of girls is 0.

Let’s calculate the number of groups for each invalid case:

For Case 1 (number of boys is less than 4):

• If there are 0 boys, then there must be $t$ girls to make a group of size $t$. The number of ways is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)\times \left(\genfrac{}{}{0ex}{}{m}{t}\right)$.
• If there is 1 boy, then there must be $t-1$ girls. The number of ways is $\left(\genfrac{}{}{0ex}{}{n}{1}\right)\times \left(\genfrac{}{}{0ex}{}{m}{t-1}\right)$.
• If there are 2 boys, then there must be $t-2$ girls. The number of ways is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\times \left(\genfrac{}{}{0ex}{}{m}{t-2}\right)$.
• If there are 3 boys, then there must be $t-3$ girls. The number of ways is $\left(\genfrac{}{}{0ex}{}{n}{3}\right)\times \left(\genfrac{}{}{0ex}{}{m}{t-3}\right)$.

For Case 2 (number of girls is 0):

• If there are 0 girls, then there must be $t$ boys. The number of ways is $\left(\genfrac{}{}{0ex}{}{n}{t}\right)\times \left(\genfrac{}{}{0ex}{}{m}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{t}\right)$.

Are these cases mutually exclusive? Yes, they are. Case 2 (girls=0) implies all $t$ actors are boys. In Case 1, we are considering cases where the number of boys is 0, 1, 2, or 3. Since $t\ge 5$, there’s no overlap.

Thus, the number of valid groups (groups with at least 4 boys and at least 1 girl) is the total number of groups minus the number of invalid groups:

$$\left(\genfrac{}{}{0ex}{}{n+m}{t}\right)-\left(\left(\genfrac{}{}{0ex}{}{n}{t}\right)\left(\genfrac{}{}{0ex}{}{m}{0}\right)+\sum _{i=0}^3\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{m}{t-i}\right)\right)$$

Also, since problem doesn’t ask to any mod, we have to do binomial coefficient without factorials in linear time. We need to be careful with the constraints of combinations. $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=0$ if $r>n$ or $r<0$. Our code should naturally handle these cases in the nCr function.

Code

ll nCr(ll n, ll r) {
  if (r > n)
    return 0;
  if (r > n - r)
    r = n - r;
  ll res = 1;
  for (ll i = 0; i < r; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
 
void solve() {
  ll n, m, t;
  cin >> n >> m >> t;
 
  ll total = nCr(n + m, t);
  ll sub = nCr(n, t);
  for (int i = 0; i <= 3; ++i) {
    sub += nCr(n, i) * nCr(m, t - i);
  }
  total -= sub;
  cout << total;
}

Related