Last Updated on March 28, 2022 by Ria Pathak
Concepts Used:
Mathematics
Difficulty Level:
Medium
Problem Statement (Simplified):
We have to find in how many ways we can arrange
Xnumber of men fromMmen andYwomen fromNwomen.
See original problem statement here
Test Case:
Input:
1
5 5 2 3
Output:
12000
Explanation:
We can select Men in 10 ways and can select women in 10 ways. We can arrange each team in 5! ways i.e. 120 ways, so we can find total arrangements in 10*10*120 ways i.e. 12000 ways.Solving Approach :
1) We can find the answer if we know, the total number of ways to select men, women, and all the possible arrangements of the team formed from both.
2) Here we need to find two things, that are:
1) The number of ways to select x items from total M items.
2) The number of arrangements we can get from total K items.3) Mathematically, we can find the number of ways to select
xitems from totalMitems by using the notation MCx. It can be calculated using the following formula.MCx =
4) We can also find the total number of ways to array
Kitems by taking the factorial of K i.e.K!.
5) So our final answer would be, the total number of ways to select required men multiplied by the total number of ways to select required women multiplied by the total number of arrangements.Answer = MCx x NCy x
(X+Y)!
Example:
We break this problem in two steps, i.e.
Selecting Ways to make a teamandFinding total number of arrangements for a team.Step 1: Selecting ways to make a team
Let’s asssume there are three men, and three women, and we have to form a team by selecting 2 men and 2 women, we can select them in these ways,
3 MEN (M1 M2 M3 ) and 3 WOMEN (W1 W2 W3 )Selecting 2 Men from 3 Men
M1 M2
M1 M3
M2 M3Selecting 2 Women from 3 Women
W1 W2
W1 W3
W2 W3Now we have selected men and women, we now form a team, for every subteam of men, we can create team with subteam of women, so there will be total
ways. Where
mis number of ways to select2men from3men, andnis number of ways to select2women from3women. Hence there are total= 9 ways.
M1 M2 + W1 W2
M1 M2 + W1 W3
M1 M2 + W2 W3M1 M3 + W1 W2
M1 M3 + W1 W3
M1 M3 + W2 W3M2 M3 + W1 W2
M2 M3 + W1 W3
M2 M3 + W2 W3Step 2: total number of arrangements for a team
Let’s take a team from above teams, i.e. M1 M3 W1 W2, We can arrange this team in following ways :M1 M3 W1 W2
M3 M1 W1 W2
W1 M1 M3 W2
M1 W1 M3 W2
M3 W1 M1 W2
W1 M3 M1 W2
W1 M3 W2 M1
M3 W1 W2 M1
W2 W1 M3 M1
W1 W2 M3 M1
M3 W2 W1 M1
W2 M3 W1 M1
W2 M1 W1 M3
M1 W2 W1 M3
W1 W2 M1 M3
W2 W1 M1 M3
M1 W1 W2 M3
W1 M1 W2 M3
M3 M1 W2 W1
M1 M3 W2 W1
W2 M3 M1 W1
M3 W2 M1 W1
M1 W2 M3 W1
W2 M1 M3 W1Hence, there are total
24ways to arrange a single team in different ways.Now, we have found both ways, so for each selected team, we can arrange them in
24ways, hence final number of selecting teams with total number of arrangements are= 216.
Solutions:
#include <stdio.h>
int nCr(int n, int r){
if(r==0)
return 1;
if(r==1 || r==n-1)
return n;
if(r > n/2)
r = n-r;
int num = 1,den = 1;
for(int i=1; i<=r; i++,n--){
num*=n;
}
for(int i=2; i<=r; i++)
den*=i;
return num/den;
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
int M,W,X,Y;
scanf("%d%d%d%d",&M,&W,&X,&Y);
long long waysOfArrangements = 1, waysOfSelection = nCr(M,X)*nCr(W,Y);
for(int i=2; i<=X+Y; i++)
waysOfArrangements*=i;
printf("%lld\n",waysOfSelection*waysOfArrangements);
}
}
#include <bits/stdc++.h>
using namespace std;
int nCr(int n, int r){
if(r==0)
return 1;
if(r==1 || r==n-1)
return n;
if(r > n/2)
r = n-r;
int num = 1,den = 1;
for(int i=1; i<=r; i++,n--){
num*=n;
}
for(int i=2; i<=r; i++)
den*=i;
return num/den;
}
int main()
{
int test;
cin>test;
while(test--){
int M,W,X,Y;
cin>M>W>X>Y;
long long waysOfArrangements = 1, waysOfSelection = nCr(M,X)*nCr(W,Y);
for(int i=2; i<=X+Y; i++)
waysOfArrangements*=i;
cout<<waysOfSelection*waysOfArrangements<<endl;
}
}
import java.util.*;
import java.io.*;
public class Main {
static int nCr(int n, int r){
if(r==0)
return 1;
if(r==1 || r==n-1)
return n;
if(r > n/2)
r = n-r;
int num = 1,den = 1;
for(int i=1; i<=r; i++,n--){
num*=n;
}
for(int i=2; i<=r; i++)
den*=i;
return num/den;
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test!=0){
int M = sc.nextInt(),W = sc.nextInt(),X = sc.nextInt(),Y = sc.nextInt();
long waysOfArrangements = 1, waysOfSelection = nCr(M,X)*nCr(W,Y);
for(int i=2; i<=X+Y; i++)
waysOfArrangements*=i;
System.out.println(waysOfSelection*waysOfArrangements);
test--;
}
}
}
[forminator_quiz id="705"]
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 MYCODE | Competitive Programming.