# 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

Mathematics

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:

$^{n}C_{r}=\frac{n!}{r!(n-r)!}$

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

}
}
`