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 x1 objects are placed in the first group, x2 objects are placed in the second group and xR objects are placed in the Rth group. It is given that,
x1 + x2 + x3 +…+ xR = N
The solution of this equation by multinomial theorem is given by N + R – 1CR – 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.
I got this website from my friend who shared with me on the topic of
this web site and now this time I am browsing this site and reading very
informative posts at this time.