Stars and Bars: Distributing Identical Objects

June 2026 · 18 min read

The Stars and Bars Theorem

Suppose you have n identical candies and you want to distribute them among k distinct children. How many ways can you do it? This is the quintessential problem that the stars and bars technique answers.

Represent each candy as a star (★) and use k − 1 dividers (bars |) to separate the stars into k groups. For example, distributing 5 candies among 3 children might look like:

★ ★ | ★ ★ ★ |        → (2, 3, 0)
| ★ ★ ★ ★ | ★      → (0, 4, 1)
★ ★ ★ ★ ★ | |      → (5, 0, 0)

Every valid arrangement of n stars and k − 1 bars corresponds to exactly one distribution. The total number of symbols is n + k − 1, and we choose where to place the k − 1 bars, giving:

C(n + k − 1, k − 1)

Equivalently, this counts the number of non-negative integer solutions to x₁ + x₂ + … + xₖ = n.

Non-negative Integer Solutions

The most common formulation in competitive programming is:

Count the number of solutions to x₁ + x₂ + … + xₖ = n where each xᵢ ≥ 0.

As established above, the answer is:

C(n + k - 1, k - 1)

Let's verify with a small example. For n = 3, k = 2, the solutions are (0,3), (1,2), (2,1), (3,0) — that's 4 = C(4,1). ✓

Here is a C++ helper that computes this quantity modulo a prime:

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;
long long fac[MAXN], inv_fac[MAXN];

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] % MOD * inv_fac[r] % MOD * inv_fac[n - r] % MOD;
}

// Number of non-negative integer solutions to x1+x2+...+xk = n
long long stars_and_bars(int n, int k) {
    return C(n + k - 1, k - 1);
}

Positive Integer Solutions

What if each child must receive at least one candy? That is, we need xᵢ ≥ 1 for all i. The standard trick is a change of variables: let yᵢ = xᵢ − 1, so yᵢ ≥ 0 and the equation becomes:

y₁ + y₂ + … + yₖ = n − k    (each yᵢ ≥ 0)

This has solutions only when n ≥ k, and the answer is:

C(n − 1, k − 1)

There is a beautiful combinatorial interpretation: place n stars in a row. There are n − 1 gaps between consecutive stars. Choose k − 1 of these gaps for the bars. Each group is automatically non-empty.

// Number of positive integer solutions to x1+x2+...+xk = n
long long stars_and_bars_positive(int n, int k) {
    if (n < k) return 0;
    return C(n - 1, k - 1);
}

Upper Bound Constraints

Things get more interesting when we add upper bounds. Suppose we need non-negative solutions to x₁ + x₂ + … + xₖ = n where each xᵢ ≤ cᵢ.

Stars and bars alone cannot handle upper bounds directly. We need to combine it with the Inclusion-Exclusion Principle (PIE).

The PIE Approach

Let Aᵢ be the set of solutions where xᵢ > cᵢ (i.e., the variable exceeds its cap). We want:

Total − |A₁ ∪ A₂ ∪ … ∪ Aₖ|

By PIE, this expands to an alternating sum. For the special case where all upper bounds are equal (cᵢ = c for all i), the formula simplifies nicely:

Answer = Σ_{j=0}^{k}  (-1)^j · C(k, j) · C(n - j·(c+1) + k - 1, k - 1)

We only include terms where n − j·(c+1) ≥ 0.

// Count solutions to x1+...+xk = n, 0 <= xi <= cap, mod prime
long long count_with_cap(int n, int k, int cap) {
    long long ans = 0;
    for (int j = 0; j <= k; j++) {
        long long rem = n - (long long)j * (cap + 1);
        if (rem < 0) break;
        long long term = C(k, j) % MOD * C(rem + k - 1, k - 1) % MOD;
        if (j & 1) ans = (ans - term % MOD + MOD) % MOD;
        else        ans = (ans + term) % MOD;
    }
    return ans;
}

Inclusion-Exclusion Extension

Let's formalize the PIE-based approach for distinct upper bounds c₁, c₂, …, cₖ. We enumerate over all subsets S ⊆ {1, 2, …, k}:

Answer = Σ_S  (-1)^|S| · C(n − Σ_{i∈S}(cᵢ+1) + k − 1,  k − 1)

For small k (≤ 20), we iterate over bitmasks:

// Distinct upper bounds: cap[i] for variable i
long long count_with_distinct_caps(int n, int k, vector<int>& cap) {
    long long ans = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        long long rem = n;
        int bits = __builtin_popcount(mask);
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i))
                rem -= cap[i] + 1;
        }
        if (rem < 0) continue;
        long long term = C(rem + k - 1, k - 1);
        if (bits & 1) ans = (ans - term + MOD) % MOD;
        else           ans = (ans + term) % MOD;
    }
    return ans;
}

Common CP Applications

1. Distributing Balls into Boxes

The classic setup: n identical balls, k distinct boxes. Constraints vary (non-negative, positive, bounded), but the core is always stars and bars.

2. Counting Multisets

The number of multisets of size n chosen from a set of k types is exactly C(n + k − 1, k − 1). This is the same as counting non-negative solutions — each type can appear any number of times.

3. Weak Compositions

A weak composition of n into k parts is an ordered tuple of non-negative integers summing to n. The count is C(n + k − 1, k − 1).

4. Counting Paths on a Grid (Variant)

Some grid-path problems reduce to distributing steps among dimensions. For example, distributing n right-steps and m up-steps to reach (n, m) from the origin is C(n + m, n), which is a special case.

5. Polynomial Coefficient Extraction

The coefficient of xⁿ in (1 + x + x² + …)ᵏ = 1/(1−x)ᵏ is C(n + k − 1, k − 1). This connection to generating functions is powerful for more complex variants.

// Example: Count ways to make change of n cents using
// unlimited coins of denominations 1..k (each coin type identical)
// This is NOT a direct stars-and-bars problem (different denominations),
// but bounded versions often reduce to it.

// Direct stars-and-bars: ways to choose n items from k types
long long multiset_count(int n, int k) {
    return C(n + k - 1, k - 1);
}

int main() {
    precompute();

    int n, k;
    cin >> n >> k;

    // Non-negative solutions
    cout << "Non-negative: " << stars_and_bars(n, k) << "\n";

    // Positive solutions
    cout << "Positive:     " << stars_and_bars_positive(n, k) << "\n";

    // Bounded (each xi <= cap)
    int cap;
    cin >> cap;
    cout << "Bounded:      " << count_with_cap(n, k, cap) << "\n";

    return 0;
}

Practice Problems

Try these problems to solidify your understanding of stars and bars:

1. Distributing Apples (CSES 1716) — Classic stars and bars. Distribute n apples into m children.
2. Candy Distribution — Given upper bounds on each child, count the number of valid distributions. Requires PIE + stars and bars.
3. Non-negative Lattice Points — Count non-negative integer points on the hyperplane x₁ + x₂ + … + xₖ = n.
4. Bounded Variables — Count solutions to x₁ + x₂ + x₃ = 100 where 0 ≤ x₁ ≤ 40, 0 ≤ x₂ ≤ 50, 0 ≤ x₃ ≤ 60.
5. Multiset Counting — How many multisets of size 10 can be formed from an alphabet of 5 letters?

Quick Reference Table