Total number of ways to form a team of size K from X men and Y women with at least 4 men and 1 woman in the team

Concepts Used:

Mathematics

Difficulty Level:

Hard

Problem Statement (Simplified):

In this problem, we have to find a total number of ways to form a team of size K from X men and Y women with at least 4 men and 1 woman in the team.

Test Case:

Input:
1
5 2 6

Output:
7

Explanation:
For example, We have to form a team of size 6(K), and there need to be at least 4 men and 1 woman out of 5(X) men and 2(Y) women. So we can form 2 teams and in total 7 ways, consisting Men and Women in the following ways :  
  4 Men + 2 Women ( Total 5 ways )  
  5 Men + 1 Women ( Total 2 ways )  

Solving Approach :

1) We already know, we can select m men and n women from X men and women in

ways, where any value

can be calculated using this formula :

2) As we know, we need to form a team of size K where there need to be at least 4 men and 1 woman at least.

3) For the above condition, there will be K-4 different teams, containing different numbers of men and women in the team.

In the first team, there would be 4 men and K-4 women, in second-team there would be 5 men and K-5 women, as we reach to end, the last team consists of K-1 men and 1 woman.

4) So, mathematically the total number of the team becomes :

Total number of teams =

Example:

Let’s assume, We have to form a team of size 6(K) and there needs to be atleast 4 men and 1 women out of 5(X) men and 2(Y) women. So we can form 2 teams, consisting Men and Women in following ways :

4 Men + 2 Women ( Total 5 ways )
5 Men + 1 Women ( Total 2 ways )

Total number of ways to form a team of size 6 with 4 Men and 2 women :

Assuming Men(M¹ M² M³ M⁴ M⁵) and Women (W¹ M²) are there to select, now we have to select team of 6, we need 2 women, so we’ll pick all women, and we need 4 men, so we’ll pick 4 men and then pair them with women. So possible ways are :

M¹ M² M³ M⁴ + W¹ W²
M¹ M² M³ M⁵ + W¹ W²
M¹ M² M⁵ M⁴ + W¹ W²
M¹ M⁵ M³ M⁴ + W¹ W²
M⁵ M² M³ M⁴ + W¹ W²

Total number of ways to form a team of size 6 with 5 Men and 1 women :

Assuming Men(M¹ M² M³ M⁴ M⁵) and Women (W¹ M²) are there to select, now we have to select team of 6, we need 5 men, so we’ll pick all men, and we need 1 woman, so we’ll pick 1 woman and then pair her with men. So possible ways are :

M¹ M² M³ M⁴ M⁴ + W¹
M¹ M² M³ M⁴ M⁴ + W¹

Hence, in similar ways, we can find answers for different cases.

Solutions:

#include <stdio.h>

long long nCr(int n, int r){
  long long value=1;
    for(int i=0;i<r;i++){
       value*=(n-i);
       value/=(i+1);
    }
    return value;
}

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n, m, k;
    scanf("%d%d%d",&n,&m,&k);

    long long sum=0;

    for(int i=4; i<k; i++){
      sum += nCr(n,i)*nCr(m,k-i);
    }

    printf("%lld\n",sum);
  }
}

#include <bits/stdc++.h>
using namespace std;

long long nCr(int n, int r){
  long long value=1;
    for(int i=0;i<r;i++){
       value*=(n-i);
       value/=(i+1);
    }
    return value;
}

int main()
{
  int test;
  cin>test;

  while(test--){

    int n, m, k;
    cin>n>m>k;

    long long sum=0;

    for(int i=4; i<k; i++){
      sum += nCr(n,i)*nCr(m,k-i);
    }

    cout<<sum<<endl;
  }
}

import java.util.*;
import java.io.*;

public class Main {

  static long nCr(int n, int r){
    long value=1;
      for(int i=0;i<r;i++){
         value*=(n-i);
         value/=(i+1);
      }
      return value;
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();

      long sum=0;

      for(int i=4; i<k; i++){
        sum += nCr(n,i)*nCr(m,k-i);
      }

      System.out.println(sum);
    }  

  }
}

[forminator_quiz id="858"]

This article tried to discuss Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out .