To distribute n identical objects into r distinct boxes: C(n+r-1, r-1) if empty boxes allowed, C(n-1, r-1) if each box must have at least one. Think of n stars and (r-1) bars as dividers. For "at least k in each box," first place k in each box (uses kr objects), then distribute remaining (n-kr) freely. Example: x+y+z = 10 with x,y,z >= 2: substitute a = x-2, b = y-2, c = z-2, solve a+b+c = 4, answer = C(6,2) = 15.
Part of ALG-07 — Permutations & Combinations
Stars and Bars Technique
Like these notes? Save your own copy and start studying with NoteTube's AI tools.
Sign up free to clone these notes