Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 05 / 09Permutations and Combinations

Distributing Identical Objects: Stars and Bars and Integer Solutions of Equations

Counting non-negative and positive integer solutions of x1 + x2 + ... + xr = n, identical objects into distinct boxes, handling lower and upper bounds by substitution and inclusion-exclusion, and the coefficient method with generating functions.

Figure 1
How many ways can nn identical objects be distributed among rr distinct boxes? Equivalently, how many solutions does x1+x2+⋯+xr=nx_{1} + x_{2} + \cdots + x_{r} = n have in non-negative integers? Here xix_{i} is the number of objects in box ii. Stars and bars. Represent a distribution as a row of nn stars (the objects) and r−1r - 1 bars (dividers between boxes). The stars before the first bar go to box 11, those between the first and second bars to box 22, and so on. The figure shows 2+3+2=72 + 3 + 2 = 7. Every arrangement of nn stars and r−1r - 1 bars gives exactly one distribution, and vice versa. The arrangement is fixed by choosing which of the n+r−1n + r - 1 positions hold the bars, so number of non-negative solutions =(n+r−1r−1)= \binom{n + r - 1}{r - 1}. For positive solutions (each xi≥1x_{i} \ge 1, no empty box), first put one object in each box, then distribute the remaining n−rn - r freely: (n−1r−1)\binom{n - 1}{r - 1}. Equivalently, choose r−1r - 1 of the n−1n - 1 gaps between nn stars in a row to place the dividers. Lower bounds: if xi≥aix_{i} \ge a_{i}, substitute yi=xi−ai≥0y_{i} = x_{i} - a_{i} \ge 0. The equation becomes ∑yi=n−∑ai\sum y_{i} = n - \sum a_{i}, which is counted by stars and bars. Upper bounds: if xi≤bix_{i} \le b_{i}, use inclusion-exclusion. Count all solutions, subtract those where some xi≥bi+1x_{i} \ge b_{i} + 1 (substitute to handle the violation), add back those where two variables violate their bounds, and so on. Alternatively, use the coefficient method: the number of solutions is the coefficient of tnt^{n} in ∏i(1+t+t2+⋯+tbi)\prod_{i}(1 + t + t^{2} + \cdots + t^{b_{i}}). Each factor lists the allowed values of one variable, and multiplying out collects the ways the exponents can add to nn. The generating function method handles any mixture of constraints, such as 'even values only' (use 1+t2+t4+⋯1 + t^{2} + t^{4} + \cdots). Useful expansions for the coefficient method: (1−t)−r=∑k≥0(k+r−1r−1)tk(1 - t)^{-r} = \sum_{k \ge 0}\binom{k + r - 1}{r - 1}t^{k} (which is stars and bars in disguise), and 1+t+⋯+tm=1−tm+11−t1 + t + \cdots + t^{m} = \frac{1 - t^{m + 1}}{1 - t}. Which model applies? This is the question that decides the answer. Identical objects into distinct boxes: stars and bars. Distinct objects into distinct boxes, any number per box: rnr^{n} (each object chooses a box). Distinct objects into distinct boxes, none empty: onto functions, ∑k(−1)k(rk)(r−k)n\sum_{k}(-1)^{k}\binom{r}{k}(r - k)^{n}. Identical objects into identical boxes: partitions of nn, counted by listing (no simple formula). Distinct objects into identical boxes: partitions of a set (Stirling numbers), usually small enough to count by cases. Key Takeaways: - x1+⋯+xr=nx_{1} + \cdots + x_{r} = n, xi≥0x_{i} \ge 0: (n+r−1r−1)\binom{n + r - 1}{r - 1}. - xi≥1x_{i} \ge 1: (n−1r−1)\binom{n - 1}{r - 1}. - Lower bounds: shift variables; upper bounds: inclusion-exclusion or the coefficient method. - Number of solutions with bounds = coefficient of tnt^{n} in ∏(1+t+⋯+tbi)\prod(1 + t + \cdots + t^{b_{i}}). - Identical into distinct: stars and bars. Distinct into distinct: rnr^{n}. - The number of terms in the expansion of (x1+⋯+xr)n(x_{1} + \cdots + x_{r})^{n} is (n+r−1r−1)\binom{n + r - 1}{r - 1}. - Pitfall: using stars and bars for distinct objects, or rnr^{n} for identical ones. Brain-Teaser 1: In how many ways can 1010 identical chocolates be given to 44 children so that each child gets at least 11 and no child gets more than 44? Solution: With xi≥1x_{i} \ge 1, substitute yi=xi−1≥0y_{i} = x_{i} - 1 \ge 0: ∑yi=6\sum y_{i} = 6 with yi≤3y_{i} \le 3. Without the upper bound: (93)=84\binom{9}{3} = 84. Subtract solutions where some yi≥4y_{i} \ge 4: set z=yi−4z = y_{i} - 4, leaving a sum of 22: (53)=10\binom{5}{3} = 10 each, times 44 children, 4040. Two variables at least 44 would need a sum of at least 8>68 > 6: impossible. So the answer is 84−40=4484 - 40 = 44. Check with the coefficient method: the coefficient of t6t^{6} in (1+t+t2+t3)4(1 + t + t^{2} + t^{3})^{4} is also 4444. Shifting for lower bounds and inclusion-exclusion for upper bounds is the standard two-step routine. Brain-Teaser 2: How many non-negative integer solutions does x+y+z=20x + y + z = 20 have with xx even? Solution: Write x=2kx = 2k, k≥0k \ge 0, with 2k≤202k \le 20. For each kk, the equation y+z=20−2ky + z = 20 - 2k has 21−2k21 - 2k non-negative solutions. Summing for k=0k = 0 to 1010: 21+19+17+⋯+1=121=11221 + 19 + 17 + \cdots + 1 = 121 = 11^{2}. A parity condition on one variable is easiest handled by summing over its allowed values; each inner count is a small stars-and-bars count. Brain-Teaser 3: How many terms are there in the expansion of (a+b+c+d)10(a + b + c + d)^{10}? How many in (1+x+x2)10(1 + x + x^{2})^{10}? Solution: A term in the first expansion is apbqcrdsa^{p}b^{q}c^{r}d^{s} with p+q+r+s=10p + q + r + s = 10, all distinct monomials, so the count is (133)=286\binom{13}{3} = 286. In the second, the terms are powers of a single variable xx, from x0x^{0} to x20x^{20}, and every power appears, giving 2121 terms. The difference is instructive: stars and bars counts distinct monomials only when the variables are independent; with one variable, many different combinations collapse onto the same power.

Practice this concept

Free · no account required · instant solutions

Distributing Identical Objects: Stars and Bars and Integer Solutions of Equations — DPP

4 questionsSee the solution the moment you answer

Practice