Program to find number of ways to distribute Objects

Here we’ll first understand the problem of calculation the number of ways to distribute objects into distinct groups, then we’ll implement the same in C++ with the help of example.

Given: 2 integers N and R, where N is the number of objects and R is the number of groups.

Problem: The task is to calculate the number of ways to distribute N identical objects into R distinct groups.

Example:

Input: N = 4, R = 2 

Output: 5 

No of objects in 1st group = 0, in second group = 4 

No of objects in 1st group = 1, in second group = 3 

No of objects in 1st group = 2, in second group = 2 

No of objects in 1st group = 3, in second group = 1 

No of objects in 1st group = 4, in second group = 0

Input: N = 4, R = 3 

Output: 15 

Solution:

We will solve the above problem using multinomial theorem.

Let us suppose that x₁ objects are placed in the first group, x₂ objects are placed in the second group and x_R objects are placed in the R^th group. It is given that,
x₁ + x₂ + x₃ +…+ x_R = N
The solution of this equation by multinomial theorem is given by ^{N + R – 1}C_{R – 1}.

C++ program to find number of ways to distribute N identical Objects in R distinct Groups:

#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 + R - 1, R - 1);
}

// Driver code
int main()
{
    int N = 4, R = 3;

    // Function call
    cout << NoOfDistributions(N, R);

    return 0;
}

OUTPUT:

15

Time Complexity: O(R)

We can use the same program to related problems like:

• calculate number of ways to distribute M mangoes among N people.

• ways to distribute N candies among K people.

• ways of distributing N identical objects in R distinct groups with no groups empty.

Comment in case of issues, concerns or suggestions.