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.

See original problem statement here

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 MARKDOWN_HASH02129bb861061d1a052c592e2dc6b383MARKDOWNHASH men and women in <img src="http://latex.codecogs.com/svg.latex?^{X}C{m}\times^{Y}C{n}" border="0" /> ways, where any value <img src="http://latex.codecogs.com/svg.latex?^{n}C{r}" border="0" /> can be calculated using this formula by referring the best sites to learn programming languages:

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 MARKDOWN_HASHbf20193137085b07680e64a4ed4a7666MARKDOWNHASH men and 1 woman.
4) So, mathematically the total number of the team becomes :
Total number of teams = <img src="http://latex.codecogs.com/svg.latex?\sum
{i=4}^{K-1}`^{X}C{i}\times^{Y}C{K-i}" border="0" />

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⁴ +
M¹ M² M³ M⁴ M⁴ +

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);
    }  

  }
}
Previous post POWERLEX
Next post First Capital Using Recursion

Leave a Reply

Your email address will not be published. Required fields are marked *