Day 51 — Stars and bars

Day 51 — Stars and bars

Stage V · concept day
Goal: Count nonnegative and positive integer solutions to \(x_1+\cdots+x_k=n\); interpret as multiset combinations and identical-item distributions; enforce upper bounds with inclusion–exclusion.

Why this matters

Distributing identical resources (CPU quanta, identical tokens, indistinguishable errors), counting multisets, and solving linear Diophantine equations in the nonnegative orthant are stars and bars. Hash bucket load vectors, integer knapsacks (counting, not optimizing), and “how many ways to make change” lite all use this template. Upper bounds force IE—linking tomorrow.

Theory

The basic problem

Count the number of integer solutions to

\[ x_1 + x_2 + \cdots + x_k = n \]

under various constraints on the \(x_i\).

Nonnegative solutions

If \(x_i\ge 0\) for all \(i\), the number of solutions is

\[ \binom{n+k-1}{k-1} = \binom{n+k-1}{n}. \]

Stars-and-bars story. Place \(n\) identical stars (units) in a row and insert \(k-1\) bars (dividers) to split them into \(k\) (possibly empty) groups. Total positions to fill: \(n+(k-1)\); choose positions for bars (or for stars):

\[ \underbrace{*\ *\ \cdots\ *}_{n\text{ stars}} \quad\text{and}\quad \underbrace{|\ \cdots\ |}_{k-1\text{ bars}}. \]

Example: \(n=5\), \(k=3\): **|*|** means \((2,1,2)\).

Bijection with multisets. A multiset of size \(n\) from \(k\) types has \(x_i\) copies of type \(i\); \(\sum x_i=n\), \(x_i\ge 0\). So multiset combinations:

\[ \binom{k+n-1}{n}. \]

Positive solutions

If \(x_i\ge 1\) for all \(i\) (and necessarily \(n\ge k\)), set \(y_i=x_i-1\ge 0\). Then

\[ (y_1+1)+\cdots+(y_k+1)=n \implies y_1+\cdots+y_k=n-k, \]

so number of positive solutions is

\[ \binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}. \]

Direct story: place \(n\) stars in a row; there are \(n-1\) gaps between them; choose \(k-1\) of those gaps to put a bar (forces nonempty groups).

Lower bounds other than 0 or 1

If \(x_i\ge c_i\), set \(y_i=x_i-c_i\ge 0\). Then \(\sum y_i = n-\sum c_i\), nonnegative count.

Upper bounds via inclusion–exclusion

Count nonnegative solutions to \(\sum_{i=1}^{k}x_i=n\) with each \(x_j\le M\).

1. Start with unrestricted nonnegative: \(N=\binom{n+k-1}{k-1}\).
   
2. Let \(A_j\) be solutions with \(x_j\ge M+1\). Set \(x_j'=x_j-(M+1)\ge 0\); then \(\sum x' + \cdots = n-(M+1)\), so \(|A_j|=\binom{(n-M-1)+k-1}{k-1}\) if \(n\ge M+1\), else \(0\).
   
3. \(|A_j\cap A_\ell|\) similarly with \(n-2(M+1)\), etc.
   
4. IE:

\[ \bigl|\overline{\text{violations}}\bigr| = N - \binom{k}{1}|A_1| + \binom{k}{2}|A_1\cap A_2| - \cdots. \]

(Full IE theory Day 52; this is the standard application.)

Distributing identical items to distinct bins

• \(n\) identical items, \(k\) distinct bins, bins may be empty: \(\binom{n+k-1}{k-1}\).
  
• Bins nonempty: \(\binom{n-1}{k-1}\).
  
• If bins are identical, you count integer partitions of \(n\) into at most \(k\) parts—harder, not stars-and-bars (no simple binomial closed form). Always check: are recipients distinguishable?

Distributing distinct items (contrast)

\(n\) distinct items to \(k\) distinct bins: \(k^n\) (each item chooses a bin)—product rule, not stars and bars.
If bins nonempty: surjections \(k!\,S(n,k)\) (Day 52).

Change-making lite

Number of ways to make \(n\) cents with denominations that are unlimited and order of coins irrelevant = nonnegative solutions with one variable per denomination—stars and bars only if every denomination is \(1\) or variables are free; with restricted coin values it is a generating-function / DP problem. Do not force stars-and-bars on arbitrary coin sets.

Worked examples

Example 1 — Nonnegative

\(x+y+z=5\), \(x,y,z\ge 0\): \(\binom{5+3-1}{3-1}=\binom{7}{2}=21\).

Example 2 — Positive

\(x+y+z=5\), \(x,y,z\ge 1\): \(\binom{5-1}{3-1}=\binom{4}{2}=6\).
List: \((1,1,3)\) and perms (3), \((1,2,2)\) and perms (3).

Example 3 — Multisets

Number of multisets of size 6 from 4 colors: \(\binom{4+6-1}{6}=\binom{9}{6}=84\).

Example 4 — Lower bounds

\(x+y+z=10\), \(x\ge 2\), \(y\ge 3\), \(z\ge 0\): set \(x'=x-2\), \(y'=y-3\); \(x'+y'+z=5\); \(\binom{5+2}{2}=\binom{7}{2}=21\).

Example 5 — One upper bound

\(x+y+z=10\), \(x,y,z\ge 0\), \(x\le 4\).
Total: \(\binom{12}{2}=66\).
\(A\): \(x\ge 5\), \(x'=x-5\), \(x'+y+z=5\): \(\binom{7}{2}=21\).
Answer: \(66-21=45\).

Example 6 — All variables capped

\(x+y+z=7\), \(0\le x,y,z\le 4\).
Total: \(\binom{9}{2}=36\).
\(A_i\): \(x_i\ge 5\): \(\binom{7-5+2}{2}=\binom{4}{2}=6\) each; \(\binom{3}{1}\cdot 6=18\).
\(A_i\cap A_j\): \(x_i,x_j\ge 5\) → sum at least 10 > 7: empty.
Answer: \(36-18=18\).

Example 7 — Identical cookies, distinct kids

10 identical cookies, 4 distinct children, any number including zero: \(\binom{10+3}{3}=\binom{13}{3}=286\).
Each child at least one: \(\binom{9}{3}=84\).

Example 8 — Distinct cookies

10 distinct cookies, 4 children: \(4^{10}\) (not stars and bars).

Example 9 — Equations with more variables

\(x_1+\cdots+x_5=3\), \(x_i\ge 0\): \(\binom{3+5-1}{3}=\binom{7}{3}=35\).

Example 10 — Bars visualization

\(n=3,k=2\): stars/bars patterns: ***|, **|*, *|**, |*** → solutions \((3,0),(2,1),(1,2),(0,3)\): \(\binom{4}{1}=4\).

Example 11 — Positive via gaps

\(x_1+x_2+x_3+x_4=10\), \(x_i\ge 1\): \(\binom{9}{3}=84\).

Example 12 — Integer compositions vs partitions

Ordered positive solutions = compositions of \(n\) into \(k\) parts: \(\binom{n-1}{k-1}\).
Unordered = partitions: different problem.

Example 13 — Two equations? (careful)

\(x+y=5\), \(x,y\ge 0\): \(6\) solutions. Not a 2D free problem—one free variable.

Example 14 — IE double cap

\(x+y=10\), \(x,y\ge 0\), \(x\le 6\), \(y\le 6\).
Total 11 solutions \((0,10)\ldots(10,0)\).
Violate \(x\ge 7\): \((7,3),(8,2),(9,1),(10,0)\) — 4; similarly \(y\ge 7\): 4; both impossible.
Answer: \(11-4-4=3\) namely \((4,6),(5,5),(6,4)\). Wait also \((4,6)\)… actually \((4,6),(5,5),(6,4)\) only if both \(\le 6\); also \((3,7)\) removed, etc. List: \((4,6),(5,5),(6,4)\)—only 3? \((7,3)\) removed. What about \((2,8)\)? Removed. Actually also \((6,4),(5,5),(4,6)\)—yes 3. But \((3,7)\) out. Hmm \((10,0)\) out. Correct: \(x\) from \(\max(0,10-6)=4\) to \(\min(10,6)=6\): three values.

Example 15 — CS loads

Distribute 12 identical requests to 3 servers, each server at most 5:
Total \(\binom{12+2}{2}=91\); \(A_i\): one server \(\ge 6\): \(x'=x-6\), sum 6: \(\binom{6+2}{2}=28\); three such; \(A_i\cap A_j\): two servers \(\ge 6\) → sum \(\ge 12\), third \(\ge 0\): sum vars after sub \(12-12=0\): \(\binom{0+2}{2}=1\) each pair; \(\binom{3}{2}=3\); triple: \(12-18<0\): 0.
Answer: \(91-3\cdot 28+3=91-84+3=10\).

Exercises

1. Nonnegative solutions: \(x+y+z+w=6\).
   
2. Positive solutions: \(x+y+z=9\).
   
3. Multisets of size 5 from 7 types.
   
4. \(x_1+\cdots+x_4=10\), each \(x_i\ge 2\).
   
5. \(x+y+z=8\), \(x\ge 0\), \(y\ge 0\), \(z\ge 0\), \(x\le 3\) (one IE/subtraction).
   
6. \(x+y+z=8\), each variable \(\le 5\).
   
7. Identical muffins to 5 distinct students, none empty, 12 muffins.
   
8. Same with empty allowed.
   
9. Distinct muffins (12 distinct) to 5 students: formula.
   
10. Draw all stars-and-bars for \(n=2\), \(k=3\).
    
11. Prove positive formula via \(y_i=x_i-1\).
    
12. Number of compositions of 7 into exactly 3 positive parts.
    
13. Number of compositions of 7 into any number of positive parts (\(2^{6}\)).
    
14. \(x+y=n\), \(x,y\ge 0\): show count is \(n+1\).
    
15. Ways to buy 10 doughnuts from 4 flavors (unlimited each, order irrelevant).
    
16. Same but at least one of each flavor.
    
17. CS: 20 identical jobs, 4 machines, each machine between 3 and 8 inclusive—set up IE.
    
18. Why partitions of 10 into 3 parts ≠ \(\binom{9}{2}\)?
    
19. Nonnegative solutions to \(x_1+\cdots+x_k=n\) with \(x_1=0\) forced.
    
20. Generate function awareness: coefficient of \(x^n\) in \((1+x+x^2+\cdots)^k=(1-x)^{-k}\).
    
21. \(x+2y+z=5\) — explain why plain stars-and-bars fails (not all coeffs 1).
    
22. Distribute 6 identical balls into 3 distinct boxes, no box more than 3.
    
23. Multiset combinations \(\binom{n+k-1}{k}\) vs \(\binom{n}{k}\)—when equal?
    
24. Challenge: positive solutions \(x_1+\cdots+x_k=n\) with each \(x_i\le M\)—write IE form.
    
25. Ice cream: 3 scoops, 5 flavors, rep OK, order irrelevant vs order relevant.

CS connection

• Load vectors: identical tasks on distinct servers → nonnegative compositions of load.
  
• Histogram counts: multiset of bucket hits.
  
• Integer resource allocation in OS / cloud quotas.
  
• Stars and bars in type inhabitation / linear logic lite: resource counting.
  
• Generating functions \((1-x)^{-k}\) encode the same counts for DP.

Common pitfalls

Pitfall	What to do instead
Distinct vs identical items	Distinct → \(k^n\); identical → stars/bars
Identical vs distinct bins	Identical bins → partitions, not \(\binom{n}{k}\)
Forgetting empty bins allowed or not	\(\ge 0\) vs \(\ge 1\) formulas
Upper bounds without IE	Subtract (and add back) systematically
Variables with coefficients \(\neq 1\)	Not pure stars-and-bars
Off-by-one in \(\binom{n+k-1}{k-1}\)	Memorize both \(\binom{n+k-1}{n}\) forms

Checkpoint

• Nonnegative formula + stars/bars story
  
• Positive formula + substitution
  
• Multiset interpretation
  
• One upper-bound IE computation by hand
  
• Distinct items contrast \(k^n\)
  
• Exercises 1–15
  
• Cold: \(x+y+z=10\) nonnegative; positive; each \(\le 6\)

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. \(\binom{6+3}{3}=\binom{9}{3}=84\).
   
2. \(\binom{8}{2}=28\).
   
3. \(\binom{7+5-1}{5}=\binom{11}{5}=462\).
   
4. \(y_i=x_i-2\), sum \(y=2\): \(\binom{2+3}{3}=\binom{5}{3}=10\).
   
5. \(\binom{11}{4}=330\).
   
6. \(\binom{12+4}{4}=\binom{16}{4}=1820\).
   
7. \(5^{12}\).
   
8. \(2^{6}=64\).
   
9. \(\binom{10+3}{3}=286\).
   
10. Multiset \(\binom{5+3-1}{3}=35\); ordered \(5^3=125\).

Deepening notes

Two pictures, one formula

Stars and bars: \(n\) stars, \(k-1\) bars, choose positions.
Weak compositions: ordered \(k\)-tuples of nonnegative integers summing to \(n\).
Same count \(\binom{n+k-1}{k-1}\).

Positive via gaps

\(n\) stars in a row create \(n-1\) interior gaps; choose \(k-1\) gaps for bars ⇒ nonempty bins \(\binom{n-1}{k-1}\).

Generating functions link

Each variable \(x_i\) contributes factor \((1+x+x^2+\cdots)=1/(1-x)\). Product \((1-x)^{-k}\); coefficient of \(x^n\) is \(\binom{n+k-1}{k-1}\).

Upper bounds checklist

1. Unrestricted nonnegative count \(N\).
   
2. For each \(j\), force \(x_j\ge M+1\) by substitution.
   
3. IE over the family \(\{A_j\}\).
   
4. Stop when remaining sum negative (term 0).

Identical vs distinct checklist

Items	Bins	Empty OK?	Count
Identical	Distinct	Yes	\(\binom{n+k-1}{k-1}\)
Identical	Distinct	No	\(\binom{n-1}{k-1}\)
Distinct	Distinct	Yes	\(k^n\)
Distinct	Distinct	No	surjections
Identical	Identical	—	partitions (harder)

Extra drills

D1. \(x_1+\cdots+x_6=4\) nonnegative.
D2. Positive solutions \(x+y+z+w=11\).
D3. \(x+y+z=9\), each \(\le 4\).
D4. 15 identical jobs, 4 servers, each ≥2.
D5. Multisets size 7 from 3 types—list when small.
D6. Why \(x+2y=5\) needs cases on \(y\).
D7. Compositions of 8 into 3 parts.
D8. IE: \(x+y+z=10\), each ≤5—compute fully.

Flash

Nonneg: \(\binom{n+k-1}{k-1}\); Pos: \(\binom{n-1}{k-1}\); Multiset size \(k\) from \(n\) types: \(\binom{n+k-1}{k}\).

Exam drill block

E1. Nonnegative solutions: \(x_1+\cdots+x_5=12\).
E2. Positive solutions: \(x_1+\cdots+x_5=12\).
E3. \(x+y+z=10\) with each \(x_i\ge 2\).
E4. Multisets of size 8 from 5 flavors.
E5. \(x+y+z=9\), each \(\le 5\)—set up IE (full count).
E6. Distinguish: identical balls / distinct bins / empty OK vs not.
E7. Number of weak compositions of 7 into 4 parts.
E8. Compositions of 7 into exactly 3 positive parts.
E9. True/false: (i) stars-bars needs identical items (ii) \(k^n\) is stars-bars (iii) upper bounds use IE.
E10. CS: distribute 15 identical requests to 4 servers, each server ≥1.

Mini solutions

E1. \(\binom{12+5-1}{12}=\binom{16}{12}=1820\).
E2. \(\binom{12-1}{5-1}=\binom{11}{4}=330\).
E3. \(y_i=x_i-2\), sum \(y=4\): \(\binom{4+3-1}{4}=15\).
E4. \(\binom{5+8-1}{8}=\binom{12}{8}=495\).
E5. Unrestricted \(\binom{11}{2}=55\); one var ≥6: \(\binom{5}{2}=10\) ×3 =30; two vars ≥6: sum −3 impossible → \(55-30=25\).
E8. \(\binom{6}{2}=15\).
E9. T (story); F (distinct items); T.
E10. Positive: \(\binom{14}{3}=364\).

Synthesis

Stars-and-bars counts identical items into distinct bins. Nonnegative ↔︎ weak compositions \(\binom{n+k-1}{k-1}\); positive ↔︎ strict \(\binom{n-1}{k-1}\) via \(y_i=x_i-1\) or gap method. Multisets are the same count rephrased. Distinct items use \(k^n\) or surjections—not stars-bars. Upper bounds: substitute and inclusion–exclusion (Day 52).

S1. Solve \(x_1+\cdots+x_4=15\), \(0\le x_i\le 6\) fully with IE.
S2. Write the generating-function one-liner for \((1-x)^{-k}\).
S3. Cold: multiset size 5 from 6; positive \(x+y+z+w=10\).

Tomorrow

Day 52 — Inclusion–exclusion: 2–3 sets, general formula, surjections, derangements as IE special case.