∑MathIntermediate

Stars and Bars

Key Points

•
Stars and Bars counts the ways to distribute n identical items into k distinct bins using combinations.
•
The basic unconstrained count is C(n+k-1, k-1), derived from placing k−1 dividers among n+k−1 positions.
•
Lower bounds $a_{i} \geq m_{i}$ are handled by subtracting the minimums first, using n' = n − Σ $m_{i}$ and applying the same formula if n' ≥ 0.
•
Upper bounds $a_{i} \leq M_{i}$ require inclusion–exclusion over subsets to enforce caps, treating overflows as ‘blocking’ at least $M_{i}$ +1 items.
•
When both lower and upper bounds exist, shift by minimums then apply inclusion–exclusion on the residual capacities.
•
If the adjusted total is negative, the answer is zero; negative ‘items’ do not exist in combinatorics.
•
In programming contests, compute combinations efficiently with factorials and modular inverses modulo a prime like 1,000,000,007.
•
For small k (≤20) and arbitrary caps, a 2^k inclusion–exclusion is practical; for large n without caps, O(1) per query after O(N) precomputation is ideal.

Prerequisites

→Binomial Coefficients — Stars and Bars reduces to evaluating combinations like \binom{n+k-1}{k-1}.
→Inclusion–Exclusion Principle — Upper bounds are enforced by alternately adding and subtracting subset counts.
→Modular Arithmetic — Contest implementations compute counts modulo a prime using factorials and inverses.
→Fast Exponentiation — Needed to compute modular inverses with Fermat’s little theorem efficiently.
→Dynamic Programming (Prefix Sums) — An alternative method for bounded distributions without modulus and when k is larger.
→Generating Functions (optional) — Provides a conceptual proof and understanding of stars-and-bars counts.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine giving n identical candies to k different kids. You don’t care which individual candy goes where—only how many candies each kid gets. Stars and Bars is the classic counting method for this. It turns the distribution problem into placing dividers (bars) among items (stars). The unconstrained case—any kid can get zero or more candies—has a beautifully simple answer: C(n+k-1, k-1). That’s the number of ways to choose the positions of k−1 bars among n+k−1 total slots. The method extends naturally to lower bounds: if kid i must get at least m_i candies, just pre-give those amounts, reducing the problem to distributing the remaining n' = n − Σ m_i candies freely. If n' is negative, there’s no valid distribution. Upper bounds (kid i gets at most M_i) are trickier. We use inclusion–exclusion: count all distributions, subtract those where at least one kid exceeds their cap by forcing them to take M_i+1 or more, then add back over-subtractions, and so on. In programming contexts like Codeforces, we usually compute results modulo a prime (e.g., 10^9+7). Efficient implementations precompute factorials and inverse factorials to evaluate combinations quickly. For bounded problems with small k (say ≤20), inclusion–exclusion over subsets is fast enough; for large n without caps, the direct formula is best.

02Intuition & Analogies

Think of n cookies (stars) lined up in a row. To split them among k kids, we insert k−1 separators (bars). Everything to the left of the first bar goes to kid 1, between bar 1 and bar 2 to kid 2, and so on. Because the cookies are identical, the only thing that matters is where the bars go. If two bars sit next to each other, that means the kid between them gets zero cookies. So, the task reduces to: choose k−1 bar positions among n+k−1 total spots (n stars + k−1 bars). That’s pure combinations. Lower bounds are like a ‘cover charge’ each kid must pay to enter a party. If kid i must get m_i cookies, hand those out first. Now you just have fewer cookies left to distribute freely. If you don’t have enough cookies to satisfy the minimums, the party can’t happen—answer is zero. Upper bounds are like ‘bucket capacities.’ If a bucket can hold at most M_i cookies, counting valid fillings directly is hard. Instead, count all fillings without worrying about the caps, then subtract the configurations where any bucket overflows. But be careful: if two buckets overflow, you subtracted those cases twice, so you must add them back—this is inclusion–exclusion. You can picture ‘forcing’ an overflow in a subset S by pre-placing M_i+1 cookies in each overflowing bucket i in S and then distributing the remaining cookies freely. If the remainder is negative, such cases don’t exist.

03Formal Definition

Let

x_{1}

x_{2}

\dots

x_{k}

be nonnegative integers with

\sum_{i = 1}^{k}

x_{i} = n

. The number of k-tuples (

x_{1}

\dots

x_{k}

) is given by

(k - 1 n + k - 1)

. This follows from a bijection between solutions and placements of k−1 bars among n+k−1 positions in a sequence of n stars and k−1 bars. With lower bounds

x_{i}

\geq

m_{i}

(

m_{i}

\in

Z_{\geq 0}

), define n' = n -

\sum_{i = 1}^{k}

m_{i}

. If n' < 0, there are no solutions. Otherwise, set

y_{i} = x_{i} - m_{i}

\geq

0 so that

\sum

y_{i} = n^{'}

. The count is

(k - 1 n ^{'} + k - 1)

. With upper bounds

x_{i}

\leq

M_{i}

(

M_{i}

\in

Z_{\geq 0}

), the count is obtained by inclusion–exclusion:

\sum_{S \subseteq [k]}

(-1)^{

∣ S ∣

}

(k - 1 n - \sum _{i \in S} ( M _{i} + 1 ) + k - 1)

, where terms with negative top parameters are interpreted as zero. For combined bounds

m_{i}

\leq

x_{i}

\leq

M_{i}

, first shift

y_{i} = x_{i} - m_{i}

and apply the upper-bounds formula with capacities

U_{i} = M_{i} - m_{i}

and total n' = n -

\sum

m_{i}

. Equivalently, the generating function viewpoint says the coefficient of

x^{n}

\prod_{i = 1}^{k}

(1 + x +

x^{2}

\dots

) equals

(k - 1 n + k - 1)

, and caps replace a factor with a truncated geometric series.

04When to Use

Unconstrained distributions of identical items into distinct bins: counting ways to split candies among kids, budget into categories, or time into tasks. Use the direct formula \binom{n+k-1}{k-1}.
Distributions with mandatory minimums per bin (x_i \ge m_i): subtract the minimums and then apply the unconstrained formula if the remainder is nonnegative.
Distributions with per-bin maximums (x_i \le M_i): use inclusion–exclusion over subsets of bins. This is practical when k is small to moderate (e.g., k \le 20) or when many caps are equal (allowing combinational simplifications).
Combined bounds (m_i \le x_i \le M_i): shift by m_i, then use inclusion–exclusion on the residual capacities.
Algorithmic practice: when you need counts modulo a prime in programming contests; precompute factorials and inverse factorials once to answer multiple queries fast. If numbers don’t fit in 64-bit and no modulus is given, use big integers and either multiplicative formulas for \binom{n}{r} or dynamic programming when caps exist.
As a proof tool: deducing identities like the hockey-stick identity, or deriving coefficients from generating functions.

⚠️Common Mistakes

Forgetting that items are identical and bins are distinct. Swapping these changes the problem; Stars and Bars does not apply to distributing distinct items.
Ignoring nonnegativity: after subtracting minimums, if n' < 0, the answer is zero—not negative or undefined. There are no ‘negative items.’
Misplacing the combination parameters: the unconstrained formula is \binom{n+k-1}{k-1} (or equivalently \binom{n+k-1}{n}). Using \binom{n}{k} is wrong here.
Off-by-one in inclusion–exclusion: the overflow threshold is M_i+1, not M_i. You force at least M_i+1 to ensure the cap is violated.
Dropping invalid terms: in inclusion–exclusion sums, when the top of the binomial is less than the bottom or negative, that term contributes zero. Failing to clamp these causes errors or modulo-undefined behavior.
Overflow in code: computing factorials or combinations without a modulus or big integers can overflow 64-bit types. Use modular arithmetic under a prime or big-integer libraries.
Recomputing factorials per test: in contests with many queries, precompute factorials and inverse factorials once up to max needed n to get O(1) per query.
Misinterpreting k=0 or n=0: there is exactly one solution when n=0 (all zeros), but zero solutions when k=0 and n>0.

Key Formulas

Stars and Bars Count

# {(x_{1}, \dots, x_{k}) \in Z_{\geq 0}^{k} : i = 1 \sum k x_{i} = n} = (k - 1 n + k - 1)

Explanation: Choose k−1 bar positions among n+k−1 slots of n stars and k−1 bars. This counts nonnegative integer solutions to a sum.

Lower-Bound Shift

n^{'} = n - i = 1 \sum k m_{i}

Explanation: After assigning each variable its minimum $m_{i}$ , you have n' items left to distribute freely. If n' is negative, there are no solutions.

Count with Lower Bounds

# = (k - 1 n ^{'} + k - 1), n^{'} \geq 0

Explanation: Once shifted by minimums, the problem reduces to the unconstrained case. The same stars-and-bars formula applies to n'.

Upper-Bound Inclusion–Exclusion

# = S \subseteq [k] \sum (- 1)^{∣ S ∣} (k - 1 n - \sum _{i \in S} ( M _{i} + 1 ) + k - 1)

Explanation: Force overflow in each subset S by placing $M_{i}$ +1 items there, then distribute the remainder freely. Alternate signs correct overcounting; invalid binomials are treated as zero.

Binomial Coefficient

(r n) = \frac{n !}{r ! ( n - r )!} = i = 1 \prod r \frac{n - r + i}{i}

Explanation: Two equivalent ways to compute combinations. The product form is numerically stable with big integers; the factorial form is efficient modulo a prime with precomputation.

Generating Function for Stars and Bars

(1 + x + x^{2} + \dots)^{k} = \frac{1}{( 1 - x ) ^{k}} = n = 0 \sum \infty (k - 1 n + k - 1) x^{n}

Explanation: The k-fold product of geometric series counts distributions. The coefficient of $x^{n}$ is the stars-and-bars number.

Hockey-Stick Identity

i = r \sum n (r i) = (r + 1 n + 1)

Explanation: Summing a diagonal in Pascal’s triangle equals the entry one row below and one column to the right. Useful in related summations.

Fermat Inverse

a^{- 1} \equiv a^{p - 2} (mod p), p prime

Explanation: Computes modular inverses under a prime modulus. Essential for dividing by factorials in modular binomial coefficients.

Binomial Boundary

(r n) = 0 if r < 0 or r > n

Explanation: Out-of-range parameters yield zero by convention. This is important when terms in inclusion–exclusion become negative.

Complexity Analysis

For unconstrained distributions, evaluating

(k - 1 n + k - 1)

modulo a prime p using factorial precomputation takes O(N) time and space to precompute fact and invfact up to

N = n + k - 1

. Each query then costs O(1) time and O(1) additional space. Using fast exponentiation for modular inverses costs O(log p) per inverse, but with precomputed inverse factorials, queries remain O(1). For problems with lower bounds only, the complexity is identical: compute n' = n − Σ

m_{i}

in O(k), then evaluate a single combination. The total per test is O(k) to sum minimums plus O(1) for the combination (after precompute), with O(1) extra space. Upper bounds require inclusion–exclusion over subsets of bins. If there are k bins, iterating all subsets takes O(2^k). For each subset, we perform O(

∣ S ∣

) work to sum capacities, which can be optimized by precomputing prefix sums or by accumulating on the fly; commonly this is O(1) amortized per subset if we precompute

M_{i}

+1 and add when building subsets, but practically O(k·2^k) time and O(1) space beyond factorial tables. This is suitable for k up to around 20–22 in contest settings. If counts must be exact without a modulus and may exceed 64-bit, using big integers with a multiplicative combination formula runs in O(r) arithmetic operations for

(r n)

. For bounded problems with large k or when 2^k is too big, dynamic programming can compute distributions in O(k·n) time and O(n) space using prefix sums, though this is typically slower than inclusion–exclusion when k is small. Memory considerations hinge on the largest n and whether factorial tables (size O(n+k)) or DP arrays (size O(n)) are used.

Code Examples

Unconstrained Stars and Bars: compute C(n+k-1, k-1) mod 1e9+7

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static const long long MOD = 1'000'000'007LL;
5 
6 long long modpow(long long a, long long e) {
7     long long r = 1;
8     while (e > 0) {
9         if (e & 1) r = (r * a) % MOD;
10         a = (a * a) % MOD;
11         e >>= 1;
12     }
13     return r;
14 }
15 
16 // Precompute factorials and inverse factorials up to N
17 struct Comb {
18     vector<long long> fact, invfact;
19     Comb(int N = 0) { if (N) init(N); }
20     void init(int N) {
21         fact.resize(N + 1); invfact.resize(N + 1);
22         fact[0] = 1;
23         for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
24         invfact[N] = modpow(fact[N], MOD - 2); // Fermat inverse
25         for (int i = N; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;
26     }
27     long long C(long long n, long long r) const {
28         if (r < 0 || r > n) return 0;
29         return (((fact[n] * invfact[r]) % MOD) * invfact[n - r]) % MOD;
30     }
31 };
32 
33 int main() {
34     ios::sync_with_stdio(false);
35     cin.tie(nullptr);
36 
37     long long n; int k;
38     if (!(cin >> n >> k)) return 0;
39     // We need combinations up to n + k - 1.
40     long long top = n + k - 1; // assume fits in 64-bit for contest constraints
41     Comb comb((int)top);
42     cout << comb.C((int)top, k - 1) << "\n";
43     return 0;
44 }
45

Implements the basic stars-and-bars formula modulo 1e9+7. We precompute factorials and inverse factorials up to n+k−1 and output C(n+k−1, k−1). Fermat’s little theorem gives modular inverses because the modulus is prime.

Time: Precomputation O(n+k), query O(1).Space: O(n+k) for factorial tables.

With minimum constraints x_i ≥ m_i: shift then count

1 #include <bits/stdc++.h>
2 using namespace std;
3 static const long long MOD = 1'000'000'007LL;
4 
5 long long modpow(long long a, long long e){ long long r=1; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1;} return r; }
6 
7 struct Comb{
8     vector<long long> fact, invfact;
9     void init(int N){ fact.assign(N+1,1); invfact.assign(N+1,1); for(int i=1;i<=N;++i) fact[i]=fact[i-1]*i%MOD; invfact[N]=modpow(fact[N], MOD-2); for(int i=N;i>=1;--i) invfact[i-1]=invfact[i]*i%MOD; }
10     long long C(long long n, long long r) const{ if(r<0||r>n) return 0; return fact[n]*invfact[r]%MOD*invfact[n-r]%MOD; }
11 };
12 
13 int main(){
14     ios::sync_with_stdio(false); cin.tie(nullptr);
15     long long n; int k; cin >> n >> k; vector<long long> m(k); long long sumM=0; for(int i=0;i<k;++i){ cin >> m[i]; sumM += m[i]; }
16     long long nprime = n - sumM; // remaining items after satisfying minimums
17     if(nprime < 0){ cout << 0 << "\n"; return 0; }
18     long long top = nprime + k - 1;
19     Comb comb; comb.init((int)top);
20     cout << comb.C((int)top, k - 1) << "\n";
21     return 0;
22 }
23

We satisfy all minimums first and reduce to distributing n' = n − Σ m_i items freely into k bins. If n' < 0 there is no solution; otherwise, we output C(n'+k−1, k−1) modulo 1e9+7.

Time: O(k) to sum minimums plus O(n'+k) precompute; O(1) to answer.Space: O(n'+k) for factorial tables.

With maximum constraints x_i ≤ M_i: inclusion–exclusion over subsets

1 #include <bits/stdc++.h>
2 using namespace std;
3 static const long long MOD = 1'000'000'007LL;
4 
5 long long modpow(long long a, long long e){ long long r=1; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1;} return r; }
6 
7 struct Comb{
8     vector<long long> fact, invfact;
9     void init(int N){ fact.assign(N+1,1); invfact.assign(N+1,1); for(int i=1;i<=N;++i) fact[i]=fact[i-1]*i%MOD; invfact[N]=modpow(fact[N], MOD-2); for(int i=N;i>=1;--i) invfact[i-1]=invfact[i]*i%MOD; }
10     long long C(long long n, long long r) const{ if(r<0||r>n) return 0; return fact[n]*invfact[r]%MOD*invfact[n-r]%MOD; }
11 };
12 
13 int main(){
14     ios::sync_with_stdio(false); cin.tie(nullptr);
15     long long n; int k; cin >> n >> k; vector<long long> M(k); for(int i=0;i<k;++i) cin >> M[i];
16     long long topMax = n + k - 1; // maximum needed for valid terms
17     Comb comb; comb.init((int)max(0LL, topMax));
18 
19     long long ans = 0;
20     // Iterate all subsets S of {0..k-1}
21     int total = 1 << k;
22     for(int mask = 0; mask < total; ++mask){
23         int bits = __builtin_popcount((unsigned)mask);
24         long long forced = 0; // sum of (M_i + 1) over i in S
25         for(int i=0;i<k;++i){ if(mask & (1<<i)) forced += (M[i] + 1); }
26         long long rem = n - forced; // remaining items after forcing overflows
27         long long ways = 0;
28         if(rem >= 0){ long long top = rem + k - 1; ways = comb.C((int)top, k - 1); }
29         if(bits % 2 == 0) ans = (ans + ways) % MOD; else ans = (ans - ways + MOD) % MOD;
30     }
31     cout << ans % MOD << "\n";
32     return 0;
33 }
34

Uses inclusion–exclusion to enforce per-bin maxima. For each subset S of bins that overflow, pre-place M_i+1 items to ensure violation, count remaining unconstrained distributions, and add/subtract based on the parity of |S|. Invalid cases where the remainder is negative contribute zero.

Time: O(k · 2^k) due to subset iteration; O(n+k) precompute.Space: O(n+k) for factorial tables; O(1) extra.

Both lower and upper bounds, exact big-integer answer via DP (no modulus)

1 #include <bits/stdc++.h>
2 #include <boost/multiprecision/cpp_int.hpp>
3 using namespace std;
4 using boost::multiprecision::cpp_int;
5 
6 // Counts the number of solutions to m_i <= x_i <= M_i, sum x_i = n, exactly (big integer)
7 int main(){
8     ios::sync_with_stdio(false); cin.tie(nullptr);
9     int k; int n; cin >> n >> k; // use int for DP sizing
10     vector<int> L(k), R(k);
11     for(int i=0;i<k;++i) cin >> L[i];
12     for(int i=0;i<k;++i) cin >> R[i];
13 
14     long long sumL = 0; bool bad = false;
15     vector<int> U(k);
16     for(int i=0;i<k;++i){
17         if(R[i] < L[i]) bad = true;
18         sumL += L[i];
19         U[i] = R[i] - L[i];
20     }
21     int nprime = n - (int)sumL;
22     if(bad || nprime < 0){ cout << 0 << "\n"; return 0; }
23 
24     // DP over variables with prefix sums to enforce 0 <= y_i <= U[i] and sum y_i = n'
25     vector<cpp_int> dp(nprime+1), ndp(nprime+1), pref(nprime+2);
26     dp[0] = 1; // zero variables, sum 0
27     for(int i=0;i<k;++i){
28         // prefix sums of dp for O(1) range sums
29         pref[0] = 0;
30         for(int s=0;s<=nprime;++s) pref[s+1] = pref[s] + dp[s];
31         for(int s=0;s<=nprime;++s){
32             int lo = max(0, s - U[i]);
33             int hi = s; // choose y_i in [max(0, s-U_i), s]
34             ndp[s] = pref[hi+1] - pref[lo];
35         }
36         dp.swap(ndp);
37         fill(ndp.begin(), ndp.end(), cpp_int(0));
38     }
39     cout << dp[nprime] << "\n";
40     return 0;
41 }
42

Shifts by minimums (x_i = L_i + y_i), then counts solutions with 0 ≤ y_i ≤ U_i summing to n' using dynamic programming. Prefix sums reduce the transition to O(1) per state, giving an exact big-integer answer without modulus. This is practical when n is a few thousands and k is moderate.

Time: O(k · n) arithmetic operations with big integers.Space: O(n) big-integer storage.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	static const long long MOD = 1'000'000'007LL;
5
6	long long modpow(long long a, long long e) {
7	long long r = 1;
8	while (e > 0) {
9	if (e & 1) r = (r * a) % MOD;
10	a = (a * a) % MOD;
11	e >>= 1;
12	}
13	return r;
14	}
15
16	// Precompute factorials and inverse factorials up to N
17	struct Comb {
18	vector<long long> fact, invfact;
19	Comb(int N = 0) { if (N) init(N); }
20	void init(int N) {
21	fact.resize(N + 1); invfact.resize(N + 1);
22	fact[0] = 1;
23	for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
24	invfact[N] = modpow(fact[N], MOD - 2); // Fermat inverse
25	for (int i = N; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;
26	}
27	long long C(long long n, long long r) const {
28	if (r < 0 \|\| r > n) return 0;
29	return (((fact[n] * invfact[r]) % MOD) * invfact[n - r]) % MOD;
30	}
31	};
32
33	int main() {
34	ios::sync_with_stdio(false);
35	cin.tie(nullptr);
36
37	long long n; int k;
38	if (!(cin >> n >> k)) return 0;
39	// We need combinations up to n + k - 1.
40	long long top = n + k - 1; // assume fits in 64-bit for contest constraints
41	Comb comb((int)top);
42	cout << comb.C((int)top, k - 1) << "\n";
43	return 0;
44	}
45

1	#include <bits/stdc++.h>
2	#include <boost/multiprecision/cpp_int.hpp>
3	using namespace std;
4	using boost::multiprecision::cpp_int;
5
6	// Counts the number of solutions to m_i <= x_i <= M_i, sum x_i = n, exactly (big integer)
7	int main(){
8	ios::sync_with_stdio(false); cin.tie(nullptr);
9	int k; int n; cin >> n >> k; // use int for DP sizing
10	vector<int> L(k), R(k);
11	for(int i=0;i<k;++i) cin >> L[i];
12	for(int i=0;i<k;++i) cin >> R[i];
13
14	long long sumL = 0; bool bad = false;
15	vector<int> U(k);
16	for(int i=0;i<k;++i){
17	if(R[i] < L[i]) bad = true;
18	sumL += L[i];
19	U[i] = R[i] - L[i];
20	}
21	int nprime = n - (int)sumL;
22	if(bad \|\| nprime < 0){ cout << 0 << "\n"; return 0; }
23
24	// DP over variables with prefix sums to enforce 0 <= y_i <= U[i] and sum y_i = n'
25	vector<cpp_int> dp(nprime+1), ndp(nprime+1), pref(nprime+2);
26	dp[0] = 1; // zero variables, sum 0
27	for(int i=0;i<k;++i){
28	// prefix sums of dp for O(1) range sums
29	pref[0] = 0;
30	for(int s=0;s<=nprime;++s) pref[s+1] = pref[s] + dp[s];
31	for(int s=0;s<=nprime;++s){
32	int lo = max(0, s - U[i]);
33	int hi = s; // choose y_i in [max(0, s-U_i), s]
34	ndp[s] = pref[hi+1] - pref[lo];
35	}
36	dp.swap(ndp);
37	fill(ndp.begin(), ndp.end(), cpp_int(0));
38	}
39	cout << dp[nprime] << "\n";
40	return 0;
41	}
42