Stars and bars

Stars and bars counts the ways to share $n$ identical items among $k$ distinct groups, such as candies among children or the solutions of x_1 + x_2 + \dots + x_k = n in non-negative integers. It writes each sharing as a row of items and dividers, so the count becomes a binomial coefficient. If a group may hold only a limited number of items, you also need inclusion–exclusion.

Explanation

Ann, Ben and Cat share 4 identical candies, and a child may get nothing. A sharing lists how many candies each child gets, in the order Ann, Ben, Cat: for example 2, 1, 1 or 0, 0, 4. How many sharings are there?

The usual way to count choices is to let each candy pick a child: 3 · 3 · 3 · 3 = 81. But the candies are identical. Giving the first candy to Ann and the second to Ben is the same sharing as giving the first to Ben and the second to Ann. Dividing by the number of repeats doesn't help either: the sharing 2, 1, 1 appears 12 times among the 81, while 4, 0, 0 appears once, so there is no single number to divide by.

Lay the 4 candies in a row and put 2 dividers among them. We call the candies stars and the dividers bars. The stars before the first bar go to Ann, those between the bars go to Ben, and those after the second bar go to Cat.

Fig. 1. A sharing of 4 candies among Ann, Ben and Cat written as a row of stars and bars. An empty share is two bars side by side, or a bar at an end.

Every sharing matches exactly one row, and every row of 4 stars and 2 bars matches exactly one sharing. So instead of sharings we can count rows. A row has 6 places, and it is fixed by which 2 of them hold bars. That is a choice of 2 places out of 6, the binomial coefficient C(6, 2) = 15. Fig. 2 shows all 15 sharings.

Fig. 2. The 15 ways to place 2 bars among 6 places. In the blue rows every child gets at least one candy.

The same works for any numbers. To share $n$ identical items among $k$ groups, put k - 1 bars between the groups. The row has n + k - 1 places, and the bars take k - 1 of them:

Choosing the places of the $n$ stars instead leads to the same number, C(n + k - 1, n). For the candies, C(4 + 3 - 1, 3 - 1) = C(6, 2).

Now every child must get at least one candy. Look at the blue rows in Fig. 2: there are 3 such sharings. In them the bars never touch each other or the ends of the row. Each bar sits in one of the 3 gaps between the 4 candies, at most one bar per gap, so there are C(3, 2) = 3 ways.

Fig. 3. When every child gets a candy, the 2 bars go into 2 of the 3 gaps between the candies.

In general, $n$ items have n - 1 gaps, and $k$ non-empty groups need k - 1 bars in different gaps: C(n - 1, k - 1). Giving each child one candy first leads to the same number: the 1 candy left is shared with empty shares allowed, C(1 + 3 - 1, 3 - 1) = C(3, 2) = 3. The same works for any minimum: if Ann must get at least 2 candies, give her 2 first and share the other 2 freely, C(2 + 2, 2) = 6 ways.

Stars and bars applies when identical items go into distinct groups and no group has an upper limit. The non-negative solutions of x_1 + x_2 + \dots + x_k = n are sharings: each variable is a child, and its value is the child's share. A sum that is at most $n$ becomes a sum equal to $n$ with one more variable for what is left over. For example, x_1 + x_2 \le 2 has 6 solutions: (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0). With x_3 = 2 - x_1 - x_2 they are the sharings of 2 items among 3 groups, C(4, 2) = 6.

Choosing with repetition is a sharing too: a cone of ice cream scoops is fixed by how many scoops of each flavour it has, so the scoops are the stars and the flavours are the groups.

A non-decreasing sequence such as 1, 1, 4 is also fixed by how many times each value appears, so its positions are the stars and its values are the groups.

Fig. 4. The sequence 1, 1, 4 as a row: value 1 appears twice, value 4 once, the other values never.

In C++

The count is a binomial coefficient, so the program takes the factorial version of C(n, k) from the binomial coefficients article, with its power, fact and inv_fact. The answer is modulo 10^9 + 7. C returns 0 when n < 0, k < 0 or k > n, so when the minimums take more items than there are, the count is 0. The input is n and k. For the candies it is:

4 3

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;   // a prime
const int MAXN = 2000000;           // at least the largest n + k - 1

long long power(long long x, long long n, long long m) {
    long long result = 1 % m;
    x %= m;
    while (n > 0) {
        if (n % 2 == 1) result = result * x % m;
        x = x * x % m;
        n /= 2;
    }
    return result;
}

vector<long long> fact(MAXN + 1), inv_fact(MAXN + 1);

long long C(long long n, long long k) {
    if (n < 0 || k < 0 || k > n) return 0;                        // no way to choose
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// n identical items into k groups, a group may stay empty
long long ways(long long n, long long k) {
    return C(n + k - 1, k - 1);                                   // choose the places of the k - 1 bars
}

int main() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[MAXN] = power(fact[MAXN], MOD - 2, MOD);
    for (int i = MAXN; i > 0; i--)
        inv_fact[i - 1] = inv_fact[i] * i % MOD;

    long long n, k;
    cin >> n >> k;               // n items, k groups
    cout << ways(n, k) << "\n";
}

The precomputation takes $O(\text{MAXN})$ time and memory, and each count takes $O(1)$. When a problem wants the exact count and it fits in long long (for example, n \le 100 and an answer up to 10^{18}), take C from Pascal's triangle in the same article instead.

Every group gets at least one item, or group i gets at least a[i]:

long long at_least_one = ways(n - k, k);     // one item per group first
long long at_least_a   = ways(n - sum_a, k); // sum_a = a[1] + ... + a[k]

The sum is at most n, as in x1 + ... + xk <= n:

long long sum_at_most = ways(n, k + 1);      // an extra group for the leftover

Non-decreasing sequences of length m with values from 1 to v:

long long sequences = ways(m, v);            // m positions, v values

Common mistakes

• Ignoring an upper limit per group. With at most 2 candies per child there are 6 sharings, but the formula still says 15. Subtract the overfull sharings with inclusion–exclusion, or count with a DP over groups and items in $O(nk)$ time using prefix sums.

• Sizing fact by the input bound. With n, k \le 10^6, fact[n + k - 1] reads past an array of 10^6 + 1 entries. Size the tables by the largest argument C gets, n + k - 1 (and n + k for the "at most n" call), as MAXN does in the template.

Similar techniques

• Inclusion–exclusion counts sharings when each group has an upper limit.

• Coin change counts sharings when the groups are identical too: 4 candies in 3 identical bags can be shared in 4 ways, not 15. These are the partitions of 4 into at most 3 parts, and no formula like this one counts them.

Practice

The last two problems, 1786 and 65, also need big-integer arithmetic.