Stars and Bars Algorithms

Stars and Bars Use Cases:

The Stars and Bars approach is based on a simple yet powerful concept. Imagine you have n identical objects (which we represent as stars) that you want to distribute into k distinct groups (which we represent as bars). The Stars and Bars theorem states that there are C(n+k-1, k-1) ways to do this, where C denotes the binomial coefficient.

This approach allows us to visualize the problem in a way that makes it easier to understand and solve. By representing the objects and groups as stars and bars, we can see the different ways the objects can be distributed among the groups.

This method becomes particularly useful in scenarios where the distribution of objects into groups follows specific constraints. Let’s explore two variations of the Stars and Bars approach to illustrate its versatility:

1. Distribution among groups where groups can have 0 objects:

Imagine you have N identical objects (which we represent as stars) that you want to distribute into K distinct groups, such that each group can have 0 to N number of elements. The Stars and Bars theorem states that there are C(N+K-1, K-1) ways to do this, where C denotes the binomial coefficient.

This approach allows us to visualize the problem in a way that makes it easier to understand and solve. By representing the objects as stars and bars, we can see the different ways the objects can be distributed among the groups.

Example:

Let’s consider an example where we have 4 identical objects (stars) and we want to distribute them into 2 distinct groups. So, all the possible distributions are:

From the above image, we can see that the number of ways to distribute 4 objects among 2 groups is same as having 5 blanks and finding the number of ways to fill those blanks with 4 stars (or 1 partition). In order to distribute N objects to K groups we will need K-1 partitions, so the total number of blanks will be (N+K-1) and number of objects to be distributed are N. Similarly, we can extend our observation to get the formula for N objects to be distributed among K groups as C(N + K – 1, N) or C(N + K – 1, K – 1).

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate C(N, R)
int C(int N, int R)
{
    R = min(R, N - R);
    int ans = 1;
    for (int i = 0; i < R; i++) {
        ans = ans * (N - i);
        ans = ans / (i + 1);
    }
    return ans;
}
 
// Function to get ways where groups can have 0 objects
int getWaysWithZero(int N, int K)
{
    return C(N + K - 1, K - 1);
}
 
 
int main()
{
    // Number of objects and groups
    int N = 4, K = 2;
    cout << "Ways to divide " << N << " objects among " << K
        << " groups such that a group can have 0 objects "
            "are "
        << getWaysWithZero(N, K) << endl;
    return 0;
}

Java

import java.util.*;
 
class GFG {
   
    // Function to calculate C(N, R)
    static int C(int N, int R) {
        // Ensure R is not greater than N - R
        R = Math.min(R, N - R);
 
        int ans = 1;
        for (int i = 0; i < R; i++) {
            ans = ans * (N - i);
            ans = ans / (i + 1);
        }
        return ans;
    }
 
    // Function to get ways where groups can have 0 objects
    static int getWaysWithZero(int N, int K) {
        // Calculate C(N + K - 1, K - 1)
        return C(N + K - 1, K - 1);
    }
 
    public static void main(String[] args) {
        // Number of objects and groups
        int N = 4, K = 2;
 
        // Display the result
        System.out.println("Ways to divide " + N + " objects among " + K +
                " groups such that a group can have 0 objects are " +
                getWaysWithZero(N, K));
    }
}

Python3

# Function to calculate C(N, R)
def C(N, R):
    R = min(R, N - R)
    ans = 1
    for i in range(R):
        ans = ans * (N - i)
        ans = ans // (i + 1)
    return ans
 
# Function to get ways where groups can have 0 objects
def getWaysWithZero(N, K):
    return C(N + K - 1, K - 1)
 
 
# Number of objects and groups
N, K = 4, 2
print("Ways to divide", N, "objects among", K,
      "groups such that a group can have 0 objects are",
      getWaysWithZero(N, K))

C#

using System;
 
class Program
{
    // Function to calculate C(N, R)
    static int C(int N, int R)
    {
        // Ensure R is not greater than N - R
        R = Math.Min(R, N - R);
 
        int ans = 1;
        for (int i = 0; i < R; i++)
        {
            ans = ans * (N - i);
            ans = ans / (i + 1);
        }
        return ans;
    }
 
    // Function to get ways where groups can have 0 objects
    static int GetWaysWithZero(int N, int K)
    {
        // Calculate C(N + K - 1, K - 1)
        return C(N + K - 1, K - 1);
    }
 
    static void Main()
    {
        // Number of objects and groups
        int N = 4, K = 2;
 
        // Display the result
        Console.WriteLine($"Ways to divide {N} objects among {K} groups such that a group can have 0 objects are {GetWaysWithZero(N, K)}");
    }
}

Javascript

function C(N, R) {
    // Ensure R is not greater than N - R
    R = Math.min(R, N - R);
 
    let ans = 1;
    for (let i = 0; i < R; i++) {
        ans = ans * (N - i);
        ans = ans / (i + 1);
    }
    return ans;
}
 
function getWaysWithZero(N, K) {
    // Calculate C(N + K - 1, K - 1)
    return C(N + K - 1, K - 1);
}
 
// Number of objects and groups
let N = 4;
let K = 2;
 
// Display the result
console.log(`Ways to divide ${N} objects among ${K} groups such that a group can have 0 objects are ${getWaysWithZero(N, K)}`);

Output

Ways to divide 4 objects among 2 groups such that a group can have 0 objects are 5

Time Complexity: O(K), where K is the number of groups among which objects are distributed.
Auxiliary Space: O(1)

2. Distribution among groups where groups cannot have 0 objects:

Imagine you have N identical objects (which we represent as stars) that you want to distribute into K distinct groups, such that each group should have at least 1 object. The Stars and Bars theorem states that there are C(N-1, K-1) ways to do this, where C denotes the binomial coefficient.

Example:

Let’s consider an example where we have 4 identical objects (stars) and we want to distribute them into 2 distinct groups such that each group should have at least one object. So, all the possible distributions are:

From the above image, we can see that the number of ways to distribute 4 objects among 2 groups such that each group should have at least one object then it is same as fixing the position of stars and then having the choice to fill one of the remaining blank with a partition. In order to distribute N objects to K groups we will fix the positions of all the N stars and out of the remaining (N-1) blanks between stars we can place (K-1) partitions in them, so the total number of blanks will be (N-1) and number of partitions to be placed would be (K-1). So, we can extend our observation to get the formula for N objects to be distributed among K groups such that each group gets at least one object as C(N – 1, K – 1).

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate C(N, R)
int C(int N, int R)
{
    R = min(R, N - R);
    int ans = 1;
    for (int i = 0; i < R; i++) {
        ans = ans * (N - i);
        ans = ans / (i + 1);
    }
    return ans;
}
 
// Function to get ways where groups cannot have 0 objects
int getWaysWithoutZero(int N, int K)
{
    return C(N - 1, K - 1);
}
 
int main()
{
    // Number of objects and groups
    int N = 4, K = 2;
    cout << "Ways to divide " << N << " objects among " << K
        << " groups such that a group cannot have 0 "
            "objects are "
        << getWaysWithoutZero(N, K) << endl;
    return 0;
}

Java

import java.util.Scanner;
 
public class Solution {
    // Function to calculate C(N, R)
    static int C(int N, int R) {
        R = Math.min(R, N - R);
        int ans = 1;
        for (int i = 0; i < R; i++) {
            ans = ans * (N - i);
            ans = ans / (i + 1);
        }
        return ans;
    }
 
    // Function to get ways where groups cannot have 0 objects
    static int getWaysWithoutZero(int N, int K) {
        return C(N - 1, K - 1);
    }
 
    public static void main(String[] args) {
        // Number of objects and groups
        int N = 4, K = 2;
        System.out.println("Ways to divide " + N + " objects among " + K +
                " groups such that a group cannot have 0 objects are " +
                getWaysWithoutZero(N, K));
    }
}
 
// This code is contributed by shivamgupta310570

Python3

import math
 
# Function to calculate C(N, R)
def C(N, R):
    R = min(R, N - R)
    ans = 1
    for i in range(R):
        ans = ans * (N - i)
        ans = ans // (i + 1)
    return ans
 
# Function to get ways where groups cannot have 0 objects
def getWaysWithoutZero(N, K):
    return C(N - 1, K - 1)
 
# Number of objects and groups
N = 4
K = 2
 
print(f"Ways to divide {N} objects among {K} groups such that a group cannot have 0 objects are {getWaysWithoutZero(N, K)}")

C#

using System;
 
class Program
{
    // Function to calculate C(N, R)
    static int C(int N, int R)
    {
        R = Math.Min(R, N - R);
        int ans = 1;
        for (int i = 0; i < R; i++)
        {
            ans = ans * (N - i);
            ans = ans / (i + 1);
        }
        return ans;
    }
 
    // Function to get ways where groups cannot have 0 objects
    static int GetWaysWithoutZero(int N, int K)
    {
        return C(N - 1, K - 1);
    }
 
    static void Main(string[] args)
    {
        // Number of objects and groups
        int N = 4, K = 2;
        Console.WriteLine($"Ways to divide {N} objects among {K} groups such that a group cannot have 0 objects are {GetWaysWithoutZero(N, K)}");
    }
}

Javascript

// Function to calculate C(N, R)
function C(N, R) {
    R = Math.min(R, N - R);
    let ans = 1;
    for (let i = 0; i < R; i++) {
        ans = ans * (N - i);
        ans = Math.floor(ans / (i + 1));
    }
    return ans;
}
 
// Function to get ways where groups cannot have 0 objects
function getWaysWithoutZero(N, K) {
    return C(N - 1, K - 1);
}
 
// Number of objects and groups
const N = 4, K = 2;
console.log("Ways to divide " + N + " objects among " + K +
            " groups such that a group cannot have 0 objects are " +
            getWaysWithoutZero(N, K));

Output

Ways to divide 4 objects among 2 groups such that a group cannot have 0 objects are 3

Time Complexity: O(K), where K is the number of groups among which objects are distributed.
Auxiliary Space: O(1)