Stars and Bars

Why Stars and Bars Matters

Suppose a service assigns five identical units of capacity to three named queues. A queue may receive nothing, and only its allocation count matters. Allocations such as $(2,0,3)$ and $(0,2,3)$ differ because the queues are labeled. How many allocation vectors are possible? Enumerating them works for a toy example, but the number grows quickly.

Stars and bars turns this allocation problem into choosing separator positions. It counts nonnegative integer solutions to a fixed-sum equation, a pattern that appears in resource allocation, inventory counts, monomials, and test-data generation. After this lesson, you will be able to recognize the model, derive its binomial coefficient, and compute the answer with the same dynamic program in Python, C++, and Java. The recurrence builds on recursion and dynamic-programming foundations: define a state, establish its boundaries, then reuse overlapping subproblems.

Core Concepts and Terminology

The inputs are integers $n\ge0$ and $k\ge0$. The exact answer counts ordered tuples $(x_1,\ldots,x_k)$ satisfying

$$ x_1+\cdots+x_k=n,\qquad x_i\ge0. $$

For $k\ge1$, write $n$ stars and $k-1$ bars in one string. The stars before the first bar belong to bin one; those between consecutive bars belong to the next bin; those after the last bar belong to the final bin. Leading, trailing, and adjacent bars are legal: they represent empty bins. Both the objects and the separators are indistinguishable within their own type.

There are $n+k-1$ positions in the string. Choosing the $k-1$ bar positions determines all remaining star positions, giving

$$ W(n,k)=\binom{n+k-1}{k-1}=\binom{n+k-1}{n}\qquad(k\ge1). $$

Handle zero bins separately. There is one empty allocation of zero objects, so $W(0,0)=1$; distributing a positive number of objects among zero bins is impossible, so $W(n,0)=0$ for $n\gt0$. With at least one bin, $W(0,k)=1$. Negative inputs are invalid. The programs return $W(n,k)\bmod M$ for the explicit modulus $M=1{,}000{,}000{,}007$, rather than the unbounded exact count.

How Stars and Bars Works, Step by Step

The combinatorial formula identifies the answer; the implementation below evaluates the same count without factorials or division. Define $F(b,s)$ as above. For $b\ge1$ and $s\ge1$, split allocations according to the last bin. If it is empty, delete that bin, leaving $F(b-1,s)$ choices. If it is nonempty, remove one object from it, leaving $F(b,s-1)$ choices. These cases are disjoint and reversible, so

$$ F(b,s)=F(b-1,s)+F(b,s-1). $$

The boundaries are $F(0,0)=1$, $F(0,s)=0$ for $s\gt0$, and $F(b,0)=1$. This is Pascal's addition rule on a rectangular state grid.

1. Reject negative inputs. Return $1$ for $n=0$, including the empty allocation when $k=0$; otherwise return $0$ for $k=0$. Return $1$ for $k=1$.
2. Allocate ways with $n+1$ entries. Set ways[0] to $1$ and all other entries to $0$: this is row $b=0$.
3. Add one labeled bin per outer iteration. Sweep totals $s=1,\ldots,n$ in ascending order.
4. Replace ways[s] by (ways[s] + ways[s - 1]) % MOD. The first term is still $F(b-1,s)$; the second has already become $F(b,s-1)$, both represented modulo $M$.
5. Keep ways[0] equal to $1$. After all $k$ iterations, return ways[n].

The direction of the sweep is part of the algorithm. During the second bin's sweep for $n=5$, the update at $s=3$ must add the old value $1$ to the already-updated value $3$, producing $4$. The figure shows that exact transition.

flowchart TD
    A["Read n and k"] --> B{"Negative input?"}
    B -- Yes --> C["Reject input"]
    B -- No --> D{"n equals zero?"}
    D -- Yes --> E["Return 1"]
    D -- No --> F{"k equals zero?"}
    F -- Yes --> G["Return 0"]
    F -- No --> H{"k equals one?"}
    H -- Yes --> E
    H -- No --> I["Initialize ways and processed = 0"]
    I --> J{"processed less than k?"}
    J -- No --> K["Return ways at n"]
    J -- Yes --> L["Set s = 1"]
    L --> N{"s at most n?"}
    N -- Yes --> O["Add current left neighbor modulo MOD"]
    O --> P["Increment s"]
    P --> N
    N -- No --> Q["Increment processed"]
    Q --> J

Worked Example with a Full Trace

Take $n=5$ and $k=3$. Every state below is smaller than $M$, so reduction does not change its value. Initialization gives [1, 0, 0, 0, 0, 0]. Each list records totals from $s=0$ through $s=5$.

For bin $b=1$, the five updates are $0+1=1$, $0+1=1$, $0+1=1$, $0+1=1$, and $0+1=1$. After each update, the array is respectively [1, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0], and [1, 1, 1, 1, 1, 1]. With one bin, every total has exactly one allocation.

For bin $b=2$, the updates are $1+1=2$, $1+2=3$, $1+3=4$, $1+4=5$, and $1+5=6$. The arrays become [1, 2, 1, 1, 1, 1], [1, 2, 3, 1, 1, 1], [1, 2, 3, 4, 1, 1], [1, 2, 3, 4, 5, 1], and [1, 2, 3, 4, 5, 6].

For bin $b=3$, the updates are $2+1=3$, $3+3=6$, $4+6=10$, $5+10=15$, and $6+15=21$. The arrays become [1, 3, 3, 4, 5, 6], [1, 3, 6, 4, 5, 6], [1, 3, 6, 10, 5, 6], [1, 3, 6, 10, 15, 6], and [1, 3, 6, 10, 15, 21].

Thus $W(5,3)=21$, agreeing with $\binom{7}{2}=21$. Another direct check fixes the first bin at $0,1,2,3,4,5$ objects: the remaining two bins admit $6,5,4,3,2,1$ allocations, whose sum is $21$.

Implementation in Python, C++, and Java

Each program defines the same count_distributions operation, uses the same boundaries and ascending updates, and prints the same samples. No input is read: the sample pairs are built in, making every panel independently runnable. In Java, save the program as Main.java.

All arithmetic is integral. Python uses arbitrary-precision integers, C++ uses long long, and Java uses BigInteger. Reduction occurs after every addition. In C++, both operands lie between $0$ and $M-1$, so their sum is at most $2M-2=2{,}000{,}000{,}012$, safely within long long; no factorial or intermediate product can overflow. Inputs must be nonnegative and the array must fit memory. Java's checked length calculation also rejects a total whose array length cannot be represented by an int.

All three programs print the following lines: modulus = 1000000007; W(0,0) = 1; W(5,0) = 0; W(0,3) = 1; W(5,1) = 1; W(5,3) = 21; W(3,5) = 35; W(4,2) = 5; W(5,5) = 126; W(30,20) = 684765627. The final value is a residue; the small preceding values equal their exact counts.

MOD = 1_000_000_007


def count_distributions(n: int, k: int) -> int:
    if n < 0 or k < 0:
        raise ValueError("n and k must be nonnegative")
    if n == 0:
        return 1
    if k == 0:
        return 0
    if k == 1:
        return 1
    ways = [0] * (n + 1)
    ways[0] = 1
    for _ in range(k):
        for total in range(1, n + 1):
            ways[total] = (ways[total] + ways[total - 1]) % MOD
    return ways[n]


def main() -> None:
    samples = [(0, 0), (5, 0), (0, 3), (5, 1), (5, 3),
               (3, 5), (4, 2), (5, 5), (30, 20)]
    print(f"modulus = {MOD}")
    for n, k in samples:
        print(f"W({n},{k}) = {count_distributions(n, k)}")


if __name__ == "__main__":
    main()

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

constexpr long long MOD = 1000000007LL;

long long count_distributions(int n, int k) {
    if (n < 0 || k < 0) {
        throw std::invalid_argument("n and k must be nonnegative");
    }
    if (n == 0) return 1;
    if (k == 0) return 0;
    if (k == 1) return 1;
    std::vector<long long> ways(static_cast<std::size_t>(n) + 1, 0);
    ways[0] = 1;
    for (int processed = 0; processed < k; ++processed) {
        for (std::size_t total = 1; total < ways.size(); ++total) {
            ways[total] = (ways[total] + ways[total - 1]) % MOD;
        }
    }
    return ways[static_cast<std::size_t>(n)];
}

int main() {
    const std::vector<std::pair<int, int>> samples = {
        {0, 0}, {5, 0}, {0, 3}, {5, 1}, {5, 3},
        {3, 5}, {4, 2}, {5, 5}, {30, 20}
    };
    std::cout << "modulus = " << MOD << '\n';
    for (const auto& sample : samples) {
        const int n = sample.first;
        const int k = sample.second;
        std::cout << "W(" << n << ',' << k << ") = "
                  << count_distributions(n, k) << '\n';
    }
    return 0;
}

import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger countDistributions(int n, int k) {
        if (n < 0 || k < 0) {
            throw new IllegalArgumentException("n and k must be nonnegative");
        }
        if (n == 0) return BigInteger.ONE;
        if (k == 0) return BigInteger.ZERO;
        if (k == 1) return BigInteger.ONE;
        BigInteger[] ways = new BigInteger[Math.addExact(n, 1)];
        Arrays.fill(ways, BigInteger.ZERO);
        ways[0] = BigInteger.ONE;
        for (int processed = 0; processed < k; ++processed) {
            for (int total = 1; total < ways.length; ++total) {
                ways[total] = ways[total].add(ways[total - 1]).mod(MOD);
            }
        }
        return ways[n];
    }

    public static void main(String[] args) {
        int[][] samples = {
            {0, 0}, {5, 0}, {0, 3}, {5, 1}, {5, 3},
            {3, 5}, {4, 2}, {5, 5}, {30, 20}
        };
        System.out.println("modulus = " + MOD);
        for (int[] sample : samples) {
            int n = sample[0];
            int k = sample[1];
            System.out.println("W(" + n + "," + k + ") = "
                    + countDistributions(n, k));
        }
    }
}

Complexity, Correctness, and Invariants

On the general path $n\gt0$ and $k\ge2$, the programs perform exactly $nk$ additions and reductions, plus array initialization. Best, average, and worst running times on that path are all $\Theta(nk)$: the allocation counts do not affect control flow. Auxiliary space is $\Theta(n)$ residues. Inputs covered by the shortcuts $n=0$, $k=0$, or $k=1$ take $\Theta(1)$ time and space. An average over arbitrary inputs needs an input distribution; there is no additional data-dependent average-case speedup.

These bounds treat the fixed modulus as constant-sized arithmetic. With a variable modulus, arithmetic also depends on its bit length. Removing every reduction computes the exact answer in Python or Java, but the growing integer sizes add bit complexity; the C++ implementation would need arbitrary-precision integers.

The formula itself has a short proof: read each allocation as a unique string and recover the allocation by counting stars in its consecutive regions. This reversible correspondence proves that choosing bar positions neither loses nor duplicates a tuple. The DP proof below shows that the programs compute the same count, including its boundaries.

Variants, Pitfalls, and Optimizations

Positive parts. If every bin must receive at least one object, set $y_i=x_i-1$. For $k\ge1$ and $n\ge k$, the answer becomes $W(n-k,k)=\binom{n-1}{k-1}$; for $n\lt k$ it is zero. For example, five objects in three nonempty bins admit $\binom{4}{2}=6$ allocations, compared with $21$ when empty bins are allowed. Zero bins still require the separate empty-allocation convention.

Arbitrary lower bounds. For $x_i\ge\ell_i$ with nonnegative integer lower bounds, subtract each bound and count $W(n-\sum_i\ell_i,k)$ if the remaining total is nonnegative. If it is negative, return zero rather than passing an invalid total into the function.

Upper bounds. A capacity restriction invalidates the unrestricted formula. For a uniform cap $0\le x_i\le u$ and $k\ge1$, inclusion-exclusion gives

$$ \sum_{j=0}^{\min(k,\lfloor n/(u+1)\rfloor)} (-1)^j\binom{k}{j} \binom{n-j(u+1)+k-1}{k-1}. $$

Each chosen violating bin is shifted down by $u+1$. For $n=5$, $k=3$, and $u=2$, the count is $21-3\binom{4}{2}=3$: the permutations of $(2,2,1)$. For unequal caps, use subset inclusion-exclusion or a DP that respects each capacity; a sliding window can accelerate the latter.

Totals at most a limit. To count tuples with $\sum_i x_i\le n$, add a slack variable representing unused capacity. The result is $W(n,k+1)=\binom{n+k}{k}$, including the single empty tuple when $k=0$.

Choose the model carefully. Distinguishable objects assigned independently to labeled bins give $k^n$ functions. Unlabeled bins require an integer-partition model, with any bin-count restriction retained. Neither is the weak-composition problem solved here.

Compute a binomial when that is cheaper. For a single large instance, the displayed DP may do too much work. Compute $\binom{N}{q}$ with $N=n+k-1$ and $q=\min(n,k-1)$ instead. An exact integer recurrence starts at $c_0=1$ and uses $c_i=c_{i-1}(N-i+1)/i$ for $1\le i\le q$; every division is exact before any final modular reduction. Under a modulus, ordinary division is invalid. Prime-modulus factorial tables require invertible factorials, so the simple method fails once the top reaches the prime; consider Lucas's theorem for that regime. The addition-only DP needs no modular inverses and also works with a composite modulus.

The other frequent implementation error is a descending sweep. Starting from the zero-bin row, one descending pass produces [1, 1, 0, 0, 0, 0] instead of [1, 1, 1, 1, 1, 1]. It has used the preceding row's left neighbor, which prevents the new bin from holding more than one object.

Practice Problems and Real-World Use

Begin with the model, then choose the computation. Identify what a star represents, whether swapping two bins changes an outcome, and whether any lower or upper bounds apply. The following are self-contained exercises and concrete uses of the same counting pattern; no external problem statement is required.

As a final check, enumerate all triples for the worked example and compare their count with the DP. Then impose the cap $2$ and verify that only $(1,2,2)$, $(2,1,2)$, and $(2,2,1)$ remain. These two small cases test both the basic bijection and the point where extra constraints require a different count.