Recuento de todas las formas posibles de elegir N personas con al menos X hombres y Y mujeres de P Hombres y Q mujeres

Posted on by Rudeus Greyrat

Dados los números enteros N , P , Q , X e Y , la tarea es encontrar el número de formas de formar un grupo de N personas que tenga al menos X hombres e Y mujeres de P hombres y Q mujeres , donde (X + Y ≤ N, X ≤ P y Y ≤ Q) .

Ejemplos:

Entrada: P = 4, Q = 2, N = 5, X = 3, Y = 1
Salida: 6
Explicación: Suponga que el grupo dado es {m1, m2, m3, m4} y {w1, w2}. Entonces las posibles combinaciones son:
m1 m2 m3 m4 w1
m1 m2 m3 m4 w2
m1 m2 m3 w1 w2
m1 m2 m4 w1 w2
m1 m3 m4 w1 w2
m2 m3 m4 w1 w2 

Por lo tanto, la cuenta es 6. 

Entrada: P = 5, Q = 2, N = 6, X = 4, Y = 1
Salida: 7

 

Enfoque: este problema se basa en la combinatoria donde necesitamos seleccionar al menos X hombres de P hombres disponibles, y al menos Y mujeres de Q mujeres disponibles, de modo que el total de personas seleccionadas sea N. Considere el ejemplo:

P = 4, Q = 2, N = 5, X = 3, Y = 1. 

En esto, las selecciones posibles son: (4 hombres de 4) * (1 mujer de 2) + (3 hombres de 4) * (2 mujeres de 2) = 4C4 * 2C1 + 4C3 * 2C2

Entonces, para algunos valores generales de P, Q y N, el enfoque se puede visualizar como:

 _{X}^{P}\textrm{C} \ast _{N-X}^{Q}\textrm{C} + _{X+1}^{P}\textrm{C} \ast _{N-X-1}^{Q}\textrm{C} + . . . + _{N-Y+1}^{P}\textrm{C} \ast _{Y-1}^{Q}\textrm{C} + _{N-Y}^{P}\textrm{C} \ast _{Y}^{Q}\textrm{C}

dónde 

_{r}^{n}\textrm{C} = \frac{n!}{r!*(n-r)!}

Siga los pasos que se mencionan a continuación para implementarlo:

  • Comience iterando un ciclo desde i = X hasta i = P.
  • Compruebe si (Ni) satisface la condición (Ni) ≥ Y y (Ni) ≤ Q . Si la condición se cumple, haga lo siguiente.
  • En cada iteración calcule el número de formas posibles si elegimos i hombres y (Ni) mujeres.
  • Para obtener el número de formas posibles para cada iteración, use la fórmula 
     

_{i}^{P}\textrm{C} \ast _{N-i}^{Q}\textrm{C}

  • Agregue este valor para cada iteración con el número total de formas.
  • Devuelva el valor total como su respuesta.

A continuación se muestra la implementación del enfoque:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate factorial
long long int fact(int f)
{
    f++;
    long long int ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
long long int ncr(int n, int r)
{
    return (fact(n) / (fact(r) * fact(n - r)));
}
 
// Function to calculate the number of ways
long long int countWays(int n, int p, int q,
                        int x, int y)
{
    // Variable to store the answer
    long long int sum = 0;
 
    // Loop to calculate the number of ways
    for (long long int i = x; i <= p; i++) {
        if (n - i >= y && n - i <= q)
            sum += (ncr(p, i) * ncr(q, n - i));
    }
    return sum;
}
 
// Driver code
int main()
{
    int P = 4, Q = 2, N = 5, X = 3, Y = 1;
 
    // Calculate possible ways for given
    // N, P, Q, X and Y
    cout << countWays(N, P, Q, X, Y) << endl;
    return 0;
}

Java

import java.util.*;
public class GFG
{
 
  // Function to calculate factorial
  static long fact(long f)
  {
    f++;
    long ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
      ans = ans * f;
    return ans;
  }
 
  // Function to calculate combination nCr
  static long ncr(long n, long r)
  {
    return (fact(n) / (fact(r) * fact(n - r)));
  }
 
  // Function to calculate the number of ways
  static long countWays(int n, int p, int q,
                        int x, int y)
  {
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (long i = x; i <= p; i++) {
      if (n - i >= y && n - i <= q)
        sum += ((int)ncr(p, i) * (int)ncr(q, n - i));
    }
    return sum;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int P = 4, Q = 2, N = 5, X = 3, Y = 1;
 
    // Calculate possible ways for given
    // N, P, Q, X and Y
    System.out.println(countWays(N, P, Q, X, Y));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Function to calculate factorial
def fact (f):
    ans = 1
 
    # Loop to calculate factorial of f
    while (f):
        ans = ans * f
        f -= 1
 
    return ans
 
# Function to calculate combination nCr
def ncr (n, r):
    return (fact(n) // (fact(r) * fact(n - r)))
 
# Function to calculate the number of ways
def countWays (n, p, q, x, y) :
 
    # Variable to store the answer
    sum = 0
 
    # Loop to calculate the number of ways
    for i in range(x, p + 1):
        if (n - i >= y and n - i <= q):
            sum += (ncr(p, i) * ncr(q, n - i))   
    return sum
 
# Driver code
P = 4
Q = 2
N = 5
X = 3
Y = 1
 
# Calculate possible ways for given
# N, P, Q, X and Y
print(countWays(N, P, Q, X, Y))
 
# This code is contributed by gfgking

C#

using System;
class GFG
{
   
// Function to calculate factorial
static long fact(long f)
{
    f++;
    long ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
static long ncr(long n, long r)
{
    return (fact(n) / (fact(r) * fact(n - r)));
}
 
// Function to calculate the number of ways
static long countWays(int n, int p, int q,
                        int x, int y)
{
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (long i = x; i <= p; i++) {
        if (n - i >= y && n - i <= q)
            sum += ((int)ncr(p, i) * (int)ncr(q, n - i));
    }
    return sum;
}
 
// Driver code
public static void Main()
{
    int P = 4, Q = 2, N = 5, X = 3, Y = 1;
 
    // Calculate possible ways for given
    // N, P, Q, X and Y
    Console.Write(countWays(N, P, Q, X, Y));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
    // Function to calculate factorial
    const fact = (f) => {
        f++;
        let ans = 1;
 
        // Loop to calculate factorial of f
        while (--f > 0)
            ans = ans * f;
        return ans;
    }
 
    // Function to calculate combination nCr
    const ncr = (n, r) => {
        return (fact(n) / (fact(r) * fact(n - r)));
    }
 
    // Function to calculate the number of ways
    const countWays = (n, p, q, x, y) => {
     
        // Variable to store the answer
        let sum = 0;
 
        // Loop to calculate the number of ways
        for (let i = x; i <= p; i++) {
            if (n - i >= y && n - i <= q)
                sum += (ncr(p, i) * ncr(q, n - i));
        }
        return sum;
    }
 
    // Driver code
 
    let P = 4, Q = 2, N = 5, X = 3, Y = 1;
 
    // Calculate possible ways for given
    // N, P, Q, X and Y
    document.write(countWays(N, P, Q, X, Y));
 
// This code is contributed by rakeshsahni
 
</script>
Producción

6

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *