Número de formas de distribuir N objetos idénticos en R grupos distintos sin grupos vacíos

Dados dos enteros N y R , la tarea es calcular el número de formas de distribuir N objetos idénticos en R grupos distintos de modo que no quede ningún grupo vacío.

Ejemplos: 

Entrada: N = 4, R = 2 
Salida:
Nº de objetos en el 1er grupo = 1, en el segundo grupo = 3 
Nº de objetos en el 1er grupo = 2, en el segundo grupo = 2 
Nº de objetos en el 1er grupo = 3, en segundo grupo = 1

Entrada: N = 5, R = 3 
Salida:
 

Enfoque: la idea es usar el teorema multinomial. Supongamos que x 1 objetos se colocan en el primer grupo, x 2 objetos se colocan en el segundo grupo y x R objetos se colocan en el grupo Rth . Se da que, 
x 1 + x 2 + x 3 +…+ x R = N para todo x i ≥ 1 para 1 ≤ i ≤ R 
Ahora reemplaza cada x i con y i + 1 para todo 1 ≤ i ≤ R . Ahora todo el yLas variables son mayores o iguales a cero. 
La ecuación se convierte en, 
y 1 + y 2 + y 3 + … + y R + R = N para todo y i ≥ 0 para 1 ≤ i ≤ R 
y 1 + y 2 + y 3 + … + y R = N – R 
Ahora se reduce a esa ecuación multinomial estándar cuya solución es (N – R) + R – 1 C R – 1
La solución de esta ecuación viene dada por N – 1 C R – 1 .

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// value of ncr effectively
int ncr(int n, int r)
{
 
    // Initialize the answer
    int ans = 1;
 
    for (int i = 1; i <= r; i += 1) {
 
        // Divide simultaneously by
        // i to avoid overflow
        ans *= (n - r + i);
        ans /= i;
    }
    return ans;
}
 
// Function to return the number of
// ways to distribute N identical
// objects in R distinct objects
int NoOfDistributions(int N, int R)
{
    return ncr(N - 1, R - 1);
}
 
// Driver code
int main()
{
    int N = 4;
    int R = 3;
 
    cout << NoOfDistributions(N, R);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.io.*;
 
class GFG
{
         
    // Function to return the
    // value of ncr effectively
    static int ncr(int n, int r)
    {
     
        // Initialize the answer
        int ans = 1;
     
        for (int i = 1; i <= r; i += 1)
        {
     
            // Divide simultaneously by
            // i to avoid overflow
            ans *= (n - r + i);
            ans /= i;
        }
        return ans;
    }
     
    // Function to return the number of
    // ways to distribute N identical
    // objects in R distinct objects
    static int NoOfDistributions(int N, int R)
    {
        return ncr(N - 1, R - 1);
    }
     
    // Driver code
    public static void main (String[] args)
    {
 
        int N = 4;
        int R = 3;
     
        System.out.println(NoOfDistributions(N, R));
    }
}
 
// This code is contributed by ajit

Python3

# Python3 implementation of the above approach
 
# Function to return the
# value of ncr effectively
def ncr(n, r):
 
 
    # Initialize the answer
    ans = 1
 
    for i in range(1,r+1):
 
        # Divide simultaneously by
        # i to avoid overflow
        ans *= (n - r + i)
        ans //= i
     
    return ans
 
# Function to return the number of
# ways to distribute N identical
# objects in R distinct objects
def NoOfDistributions(N, R):
 
    return ncr(N - 1, R - 1)
 
# Driver code
 
N = 4
R = 3
 
print(NoOfDistributions(N, R))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the above approach
using System;
 
class GFG
{
     
    // Function to return the
    // value of ncr effectively
    static int ncr(int n, int r)
    {
     
        // Initialize the answer
        int ans = 1;
     
        for (int i = 1; i <= r; i += 1)
        {
     
            // Divide simultaneously by
            // i to avoid overflow
            ans *= (n - r + i);
            ans /= i;
        }
        return ans;
    }
     
    // Function to return the number of
    // ways to distribute N identical
    // objects in R distinct objects
    static int NoOfDistributions(int N, int R)
    {
        return ncr(N - 1, R - 1);
    }
     
    // Driver code
    static public void Main ()
    {
        int N = 4;
        int R = 3;
     
        Console.WriteLine(NoOfDistributions(N, R));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to return the
// value of ncr effectively
function ncr(n, r)
{
     
    // Initialize the answer
    let ans = 1;
 
    for(let i = 1; i <= r; i += 1)
    {
         
        // Divide simultaneously by
        // i to avoid overflow
        ans *= (n - r + i);
        ans = parseInt(ans / i);
    }
    return ans;
}
 
// Function to return the number of
// ways to distribute N identical
// objects in R distinct objects
function NoOfDistributions(N, R)
{
    return ncr(N - 1, R - 1);
}
 
// Driver code
let N = 4;
let R = 3;
 
document.write(NoOfDistributions(N, R));
 
// This code is contributed by rishavmahato348
 
</script>
Producción: 

3

 

Complejidad de tiempo: O(R)

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por CrazyPro 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 *