Stars and bars

Why this matters when you build with AI

Many contest and product questions are about splitting a total into parts: how many ways to hand out n identical items to k people, with limits on each person. Once the statement is written as a sum, the count is a short formula. An AI tool often writes the formula for the unbounded case and skips the limits. The code compiles and matches the sample, because the sample's limits happen to be loose. On the real input the answer is too big.

We saw this in our own runs. For the example below, with 30 items, five boxes and per-box limits, the plain formula C(34, 4) gives 46376. The true count with the limits is 2376. Both numbers are correct for different questions, and the code needs the second one. Nothing in the first formula warns you about the limits.

This lesson covers the bars model, the three forms of the count (non-negative, positive and bounded), and a worked example with a stress test against enumeration. The code is C++17, compiled with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2 in our scratch folder. The outputs below are from those runs. Timings depend on the machine, and the counts do not.

The bars model

Start with a sum. Count the vectors (x_1, ..., x_k) of non-negative integers with x_1 + ... + x_k = n. A non-negative integer is zero or more. Take n stars and k - 1 bars. Put the bars in a row with the stars. The stars before the first bar are x_1, the stars between the first and second bars are x_2, and so on. Each row of stars and bars is one solution, and each solution is one row.

Example with n = 4 and k = 3. The row **|*|* has 2 stars, then a bar, then 1 star, then a bar, then 1 star. That is the solution (2, 1, 1). The row ||**** has two bars at the start, so the solution is (0, 0, 4). A row has n + k - 1 = 6 symbols, and we choose which k - 1 = 2 of them are bars. So the count is C(6, 2) = 15.

This gives the first formula. The number of non-negative solutions to x_1 + ... + x_k = n is C(n + k - 1, k - 1).

The second form is for positive integers, where every x_i is at least 1. Subtract 1 from each variable. The new variables are non-negative and sum to n - k. Apply the first formula with n - k in place of n:

positive solutions of x_1 + ... + x_k = n: C(n - 1, k - 1)

Example: x_1 + x_2 + x_3 = 4 with each x_i at least 1. The formula gives C(3, 2) = 3, and the three solutions are (2, 1, 1), (1, 2, 1) and (1, 1, 2). The brute force in our stress test also gave 3.

Turning a statement into the model

Most of the work is reading the statement. Three checks catch most mistakes.

1. Are the items identical or distinct? Stars and bars counts identical items. If each candy is different, the count is a different problem, and this model does not apply.
2. Is each part at least 0 or at least 1? Use the non-negative formula for "zero or more" and the positive formula for "at least one".
3. Is the answer a count of vectors or of arrangements? Two people getting 2 and 1 candies are one vector (2, 1), and it is one solution even if we later think of the people as a set.

Two worked statements:

• "How many multisets of size 4 can be chosen from 3 types?" A multiset of size 4 is a choice of how many of each type. Let x_i be the number of type i. Then x_1 + x_2 + x_3 = 4 with each x_i at least 0. The answer is C(6, 2) = 15.
• "Ten candies go to three children, and each child gets at least one." Let x_i be the candies of child i, with x_i at least 1. Then the answer is C(9, 2) = 36.

Bounds on the variables

The unbounded formulas break as soon as there is a limit. The idea is to remove the limits with a substitution, then count violations with inclusion-exclusion.

Lower bounds by substitution

Suppose x_i must be at least l_i. Write x_i = l_i + y_i, where y_i is non-negative. The sum becomes y_1 + ... + y_k = n - (l_1 + ... + l_k). If that number is negative, there are no solutions. Otherwise apply the non-negative formula with the smaller total. Positive solutions are the special case l_i = 1.

Upper bounds by inclusion-exclusion

Suppose x_i must be at most c_i. First do the lower bound shift with l_i = 0, so y_i = x_i. Let u_i = c_i. A solution breaks the bound on box i when y_i is at least u_i + 1. Let the event E_i be "y_i >= u_i + 1". We want the number of solutions in no event. This is the same principle as in the previous lesson.

For a subset S of boxes, count the solutions where every box in S breaks its bound. Write y_i = (u_i + 1) + z_i for i in S, with z_i non-negative. The sum of the z's and the other variables is n - sum over S of (u_i + 1). That count is the non-negative formula with the new total. So

answer = sum over subsets S of (-1)^|S| * C(R_S + k - 1, k - 1), where R_S = n - sum over i in S of (u_i + 1)

When R_S is negative, the term is 0. Our code handles this explicitly with a check.

Worked example: muffins into boxes

A bakery packs 30 identical muffins into 5 boxes. The boxes are different. Each box has a lower and an upper limit:

Count the ways to choose the number of muffins in each box, so that the total is 30 and each box is within its limits.

Input: a first line with n k (n at most 200000, k at most 20). Then k lines, each with the lower and the upper limit of one box. Output: one number, modulo 1000000007.

The full solution follows. It reduces the lower bounds first, then runs inclusion-exclusion over the boxes. Save it as solution.cpp.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll MOD = 1000000007LL;
 
ll power(ll b, ll e) {
    b %= MOD;
    if (b < 0) b += MOD;
    ll r = 1;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}
 
// Factorials and inverse factorials up to N. MOD is prime.
struct Comb {
    vector<ll> f, inv;
    explicit Comb(int N) : f(N + 1), inv(N + 1) {
        f[0] = 1;
        for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
        inv[N] = power(f[N], MOD - 2);
        for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    }
    ll C(ll n, ll k) const {
        if (n < 0 || k < 0 || k > n) return 0;
        return f[n] * inv[k] % MOD * inv[n - k] % MOD;
    }
};
 
// Count integer vectors x_0..x_{k-1} with sum n and lo[i] <= x_i <= hi[i].
// Shift to y_i = x_i - lo[i], so 0 <= y_i <= u_i with u_i = hi[i] - lo[i] and sum y = N.
// Then inclusion-exclusion over the boxes that break their upper bound (y_i >= u_i + 1).
ll count_bounded(ll n, const vector<ll>& lo, const vector<ll>& hi, const Comb& cb) {
    int k = lo.size();
    ll N = n;
    vector<ll> u(k);
    for (int i = 0; i < k; i++) {
        if (lo[i] > hi[i]) return 0;
        N -= lo[i];
        u[i] = hi[i] - lo[i];
    }
    if (N < 0) return 0;
    ll ans = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        // Boxes in mask are forced to have y_i >= u_i + 1. Remove that much from the total.
        ll rest = N;
        for (int i = 0; i < k; i++)
            if (mask >> i & 1) rest -= u[i] + 1;
        if (rest < 0) continue;
        // Stars and bars: rest stars into k boxes is C(rest + k - 1, k - 1).
        ll term = cb.C(rest + k - 1, k - 1);
        ans = (__builtin_popcount(mask) % 2 == 1) ? (ans - term + MOD) % MOD
                                                  : (ans + term) % MOD;
    }
    return ans;
}
 
// Input: n k, then k lines "lo hi". Output: the count modulo 1000000007.
int main() {
    ll n;
    int k;
    cin >> n >> k;
    vector<ll> lo(k), hi(k);
    for (int i = 0; i < k; i++) cin >> lo[i] >> hi[i];
    Comb cb(n + k + 1);
    cout << count_bounded(n, lo, hi, cb) << "\n";
    return 0;
}

The sample input is 30 5 followed by the five lines 0 8, 1 6, 0 10, 2 5 and 0 30. The program printed:

2376

A brute force that walks all 73656 vectors inside the limits and keeps the ones with sum 30 also gives 2376. The Python version of that check is below.

Table size

The binomial in the formula has top n + k - 1 at most, so the factorial table must reach that value. The solution builds the table up to n + k + 1, which covers it. A table that stops at n gives a wrong answer or an out-of-range read when k is large.

Testing against enumeration

The stress test generates random inputs with up to 4 boxes and totals up to 12, runs the solution, and compares with a brute force. The brute force walks every vector inside the limits and counts the ones with sum n. It is slow in general, so it is only for small inputs.

// Brute force: walk every vector inside the box limits and keep the ones with sum n.
ll brute_bounded(ll n, const vector<ll>& lo, const vector<ll>& hi) {
    int k = lo.size();
    for (int i = 0; i < k; i++) if (lo[i] > hi[i]) return 0;
    vector<ll> x = lo;
    ll cnt = 0;
    while (true) {
        ll s = 0;
        for (ll v : x) s += v;
        if (s == n) cnt++;
        int i = 0;
        while (i < k && x[i] == hi[i]) { x[i] = lo[i]; i++; }
        if (i == k) break;
        x[i]++;
    }
    return cnt % MOD;
}

The empty-range check at the top is needed. Without it, a box with lo greater than hi never reaches its upper value, and the loop never ends. Our first version of this harness hung in exactly that way, and we had to stop it. The solution returns 0 for such a box, which is the correct count.

The stress run printed:

nonneg x1+x2+x3=4: formula 15, brute 15
pos   x1+x2+x3=4: formula 3, brute 3
bounded distributions: 4000 random cases agree with enumeration
k=20, n=200000, no bounds except 0..200000: 195589730

The last line has no brute force, since 21 values per box are too many to enumerate. It is still a useful check. Every box allows up to 200000, and the total is 200000, so no box can break its bound. The bounds never bite, and the answer must equal the plain formula C(200019, 19). The solution computed 195589730 for that input, which matches the plain formula. The next Python snippet checks the formula on small cases, and it runs without input:

Its output was:

4 [0, 0, 0] [4, 4, 4] formula 15 brute 15
4 [1, 1, 1] [4, 4, 4] formula 3 brute 3
10 [1, 1, 1] [10, 10, 10] formula 36 brute 36
7 [0, 0, 0, 0] [2, 2, 2, 2] formula 4 brute 4
30 [0, 1, 0, 2, 0] [8, 6, 10, 5, 30] formula 2376 brute 2376

Complexity

The inclusion-exclusion loop takes O(2^k * k) time. With k at most 20 that is about 2 * 10^7 steps. The factorial table takes O(n + k) time and memory. For n = 200000 and k = 20, the stress run finished quickly on our machine. Timings depend on the machine.

Common mistakes

1. Using the plain formula when there are limits. The symptom is an answer that is too big. For the muffin example, the plain formula gives 46376 and the true count is 2376. Check each limit in the statement before you pick the formula.

2. Forgetting to subtract the lower bounds. If the total is not reduced by the lower bounds, the count is for a different sum. Shift each variable first, as in the solution.

3. Letting a negative remainder reach the formula. If R_S is negative, the term must be 0. Our binomial returns 0 for a negative top, so this case is safe here. Other code that does not check may index a table with a negative number.

4. A factorial table that is too small. The binomial top is n + k - 1 at most. A table of size n for n = 200000 and k = 20 would read past the end. Size the table to n + k + 1.

5. An empty range. A box with lo greater than hi has no valid value, so the answer is 0. Check it before the loop. The hang we saw in the brute force came from exactly this case.

6. A flipped sign. The inclusion-exclusion sign is the parity of the number of boxes in S. For the muffin example, one wrong sign gives a different number, and the stress test catches it on the first random case that has a violation.

Checklist

• Write the statement as a sum with one variable per part.
• Decide if each part is at least 0 or at least 1, and if the items are identical.
• Shift lower bounds first, and check that the reduced total is not negative.
• For upper bounds, list the violating sets as inclusion-exclusion events, and skip those with a negative remainder.
• Size the factorial table to n + k + 1.
• Compare with an enumeration on random small inputs, including empty ranges and boxes with a zero limit.

Exercise

Write your own bounded-distribution problem. Choose a total n, a number of boxes k at most 8, and a lower and upper limit for each box. Write a short statement with real numbers in it. Then solve it with the code above, and stress it against an enumeration on 1000 random inputs with n at most 15 and k at most 4. Your answer must match on every case.

Your deliverables are the statement, the solution run on your sample, and the stress loop with its output. Include one case where a lower bound is positive and one where an upper bound is tight.

Here is a prompt for an AI tool that may help you write the harness. Read the output before you run it, since the tool may use limits outside the statement.

Here is a counting problem: distribute n identical items into k distinct boxes
with lower and upper limits per box. Write a C++17 program that counts the
distributions using lower-bound substitution and inclusion-exclusion over the
boxes that break their upper bound, with binomials from a factorial table
modulo 1000000007. Then write a brute force that enumerates every vector inside
the limits and counts those with sum n. Write a random generator with a fixed
seed for k at most 4, n at most 15, and limits from 0 to 4 that sometimes have
lo greater than hi. Print the failing input when the two disagree. Show the real
output, not an expected one.

A good answer subtracts the lower bounds before the loop, returns 0 for empty ranges, and sizes the table from n and k. Check that the brute force has its empty-range guard before the loop.

Show the answer

Build the solution from the worked example, the brute force from the stress section, and a generator that prints the failing input. Run the loop with for seed in $(seq 1 1000) and pass the seed to the generator. A correct run prints no mismatch lines. If it prints one, check the lower-bound shift, the empty-range guard, and the table size.

Practice problems

1. How many non-negative integer solutions are there to x_1 + x_2 + x_3 = 10 with x_1 at most 4?

   Show the answer

   Hint: the unbounded count is C(12, 2) = 66. The violating solutions have x_1 at least 5, which leaves a total of 5, so there are C(7, 2) = 21 of them. The answer is 66 - 21 = 45.

2. How many positive integer solutions are there to x_1 + x_2 + x_3 + x_4 = 9?

   Show the answer

   Hint: the positive formula is C(n - 1, k - 1) with n = 9 and k = 4. That gives C(8, 3) = 56.

3. How many integer solutions are there to x_1 + x_2 = 7 with 2 at most x_1 at most 4 and x_2 at least 0?

   Show the answer

   Hint: set lo = (2, 0) and hi = (4, 7). The reduced total is 7 - 2 = 5, and the upper widths are u = (2, 7). The unbounded count is C(6, 1) = 6. Box 1 violates when its shifted value is at least 3, which leaves a total of 2, so C(3, 1) = 3 solutions break the bound. Box 2 cannot violate, since 5 - 8 is negative. The answer is 6 - 3 = 3. The solutions are x_1 = 2, 3, 4 with x_2 = 5, 4, 3.

4. Three children share 12 sweets. Each child gets at least 2 and at most 5. How many ways are there?

   Show the answer

   Hint: shift each child by 2, so y_i is between 0 and 3 and the total is 12 - 6 = 6. The unbounded count is C(8, 2) = 28. Each single violation (y_i at least 4) leaves a total of 2, so C(4, 2) = 6 solutions, and there are 3 such boxes, giving 18. Two violations need a total of at least 8, which is more than 6, so there are none. The answer is 28 - 18 = 10. Listing the values confirms this: the triples are the permutations of (3, 3, 0), (3, 2, 1) and (2, 2, 2), which give 3 + 6 + 1 = 10.

Summary

Stars and bars turns a sum into a row of stars and bars, and that gives a binomial count. Lower bounds are removed by a shift, and upper bounds by inclusion-exclusion over the boxes that break them. The table must reach n + k - 1, and every case with a negative remainder or an empty range has to return 0.