How many ways can you hand out $10$ identical cookies to $4$ children? The cookies are interchangeable, so only the amounts matter. The trick is the same as for lattice paths: match each distribution with a string and count the strings.
Key idea
The number of ways to put $n$ identical items into $k$ different boxes is $\binom{n+k-1}{k-1}$; this is also the number of solutions of $x_{1} + x_{2} + \cdots + x_{k} = n$ in nonnegative integers. If every box must get at least one item, it is $\binom{n-1}{k-1}$.
Why it works
Line up the $n$ items as stars and separate them into $k$ groups with $k - 1$ bars: $\star\star \mid \star \mid\mid \star\star\star$ means $2, 1, 0, 3$. Every distribution gives exactly one row of $n$ stars and $k - 1$ bars, and every such row gives a distribution. A row has $n + k - 1$ spots, and choosing which $k - 1$ hold bars decides it: $\binom{n+k-1}{k-1}$. It is a lattice path in disguise, with stars as R's and bars as U's. With a minimum of one per box, give each box its item first; the remaining $n - k$ items are shared freely: $\binom{n-1}{k-1}$.
Worked examples
Worked example: Cookies
In how many ways can $10$ identical cookies be given to $4$ children (some may get none)?
- $10$ stars and $3$ bars: $13$ spots.
- $\binom{13}{3} = 286$.
Answer: $286$
Worked example: At least one each
Same question, but each child gets at least one cookie.
- Give each child one cookie first; $6$ remain.
- Share $6$ among $4$: $\binom{6+3}{3} = \binom{9}{3} = 84$. (This matches $\binom{n-1}{k-1} = \binom{9}{3}$.)
Answer: $84$
Worked example: An equation with minimums
How many integer solutions does $x_{1} + x_{2} + x_{3} = 12$ have with $x_{1} \ge 2$, $x_{2} \ge 1$, $x_{3} \ge 0$?
- Hand out the minimums: $2 + 1 + 0 = 3$, leaving $9$.
- Write $x_{1} = 2 + y_{1}$, $x_{2} = 1 + y_{2}$, $x_{3} = y_{3}$ with every $y_{i} \ge 0$: then $y_{1} + y_{2} + y_{3} = 9$.
- $\binom{9+2}{2} = \binom{11}{2} = 55$.
Answer: $55$
Common mistake
Using stars and bars for different items, or forgetting the minimums. Giving $5$ different books to $3$ students is $3^{5} = 243$ (each book picks a student), not $\binom{7}{2} = 21$; stars cannot tell items apart. And with "at least one each," counting $\binom{n+k-1}{k-1}$ includes the distributions where a box is empty. Check: are the items interchangeable? Then stars and bars. Are there minimums? Hand them out first.