Arrange Ways

Concepts Used:

Mathematics

Difficulty Level:

Medium

Problem Statement (Simplified):

We have to find in how many ways we can arrange X number of men from M men and Y women from N women.

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 x items from total M items 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 K items 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 by referring some best sites to learn coding, i.e. Selecting Ways to make a team and Finding 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 M3

Selecting 2 Women from 3 Women
W1 W2
W1 W3
W2 W3

Now 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 m is number of ways to select 2 men from 3 men, and n is number of ways to select 2 women from 3 women. Hence there are total = 9 ways.

M1 M2 + W1 W2
M1 M2 + W1 W3
M1 M2 + W2 W3

M1 M3 + W1 W2
M1 M3 + W1 W3
M1 M3 + W2 W3

M2 M3 + W1 W2
M2 M3 + W1 W3
M2 M3 + W2 W3

Step 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 W1

Hence, there are total 24 ways to arrange a single team in different ways.

Now, we have found both ways, so for each selected team, we can arrange them in 24 ways, 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--;
      }

  }
}
Previous post First Capital Using Recursion
Next post Pairs

Leave a Reply

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