Stars and Bars: 12 Practice Problems with Solutions

We need the non-negative solutions of $x_1+x_2+x_3+x_4=10$. There are 10 stars and $4-1=3$ bars, so 13 symbols in a row, and we choose which 3 of them are bars:

$$\binom{13}{3}=\frac{13\cdot 12\cdot 11}{3\cdot 2\cdot 1}=286.$$

Answer: 286

Hand out one candy to each child. That uses 4 candies, and 6 remain with no restriction. Now count non-negative solutions of $y_1+y_2+y_3+y_4=6$:

$$\binom{6+3}{3}=\binom{9}{3}=84.$$

The direct formula gives the same result: $\binom{n-1}{k-1}=\binom{9}{3}=84$.

Answer: 84

Line up 15 stars. There are 14 gaps between them, and we place 2 bars in two different gaps (no empty group allowed):

$$\binom{14}{2}=91.$$

Answer: 91

A box is described by how many donuts of each flavor it holds: $x_1+\dots+x_6=8$ with $x_i\ge 0$. The 8 donuts are the stars and the 6 flavors are the boxes, so we need 5 bars:

$$\binom{8+5}{5}=\binom{13}{5}=1287.$$

This is the formula for combinations with repetition: choosing $r$ items from $m$ types gives $\binom{r+m-1}{r}$.

Answer: 1287

With $y_1=x_1-2\ge 0$, $y_2=x_2-3\ge 0$ and $y_3=x_3$, the equation becomes

$$y_1+y_2+y_3=20-2-3=15.$$

Each solution in $y$ gives exactly one solution in $x$, so the count is

$$\binom{15+2}{2}=\binom{17}{2}=136.$$

Answer: 136

Introduce a slack variable $s=12-(x_1+x_2+x_3)\ge 0$. Solutions of the inequality match one to one with non-negative solutions of

$$x_1+x_2+x_3+s=12.$$

That is 12 stars and 3 bars:

$$\binom{15}{3}=455.$$

Answer: 455

Each term is $x^a y^b z^c$ with $a+b+c=6$ and $a,b,c\ge 0$, and different exponent triples give different terms. So we count non-negative solutions with 6 stars and 2 bars:

$$\binom{8}{2}=28.$$

Answer: 28

Let $x_j$ be the number of dice showing face $j$. Then $x_1+\dots+x_6=4$ with $x_j\ge 0$: 4 stars and 5 bars.

$$\binom{9}{5}=\binom{9}{4}=126.$$

Do not confuse this with $6^4=1296$, which counts ordered results of 4 different dice.

Answer: 126

Sorting removes the order, so the sequence is just a multiset of 4 values chosen from 9. Let $c_v$ count how often value $v$ appears: $c_1+\dots+c_9=4$, $c_v\ge 0$. That is 4 stars and 8 bars:

$$\binom{12}{4}=495.$$

Answer: 495

All solutions: $\binom{12}{2}=66$.

Bad solutions: if $x_1\ge 6$, set $y_1=x_1-6$. Then $y_1+x_2+x_3=4$, which has $\binom{6}{2}=15$ solutions. The same holds for $x_2$ and $x_3$, giving $3\cdot 15=45$.

Two variables cannot both be $\ge 6$, because $6+6=12>10$. So nothing was removed twice, and by inclusion–exclusion:

$$66-45=21.$$

Answer: 21

Write the number as $abc$ with $a\ge 1$ and $a,b,c\le 9$. Put $a'=a-1\ge 0$:

$$a'+b+c=9.$$

Without upper limits there are $\binom{11}{2}=55$ solutions. Since the sum is 9, $b$ and $c$ can never exceed 9. But $a'$ must stay at most 8 (because $a\le 9$), and $a'=9$ happens in exactly one solution: $a'=9, b=c=0$, which would mean $a=10$. Removing it:

$$55-1=54.$$

Answer: 54

Lower bounds: put 2 balls in each box. That uses 8, so 7 remain: $y_1+y_2+y_3+y_4=7$, $y_i\ge 0$, where $y_i=x_i-2$.

The condition $x_1\le 5$ becomes $y_1\le 3$.

All solutions: $\binom{10}{3}=120$.

Bad solutions ($y_1\ge 4$): set $z_1=y_1-4$, so $z_1+y_2+y_3+y_4=3$, which has $\binom{6}{3}=20$ solutions.

$$120-20=100.$$

Answer: 100