Splitting fifteen tokens into three piles

Question

You split 15 identical tokens into 3 labeled piles (pile A, pile B, pile C). A pile may be empty. How many ways can this be done? (Equivalently, how many non-negative integer solutions does a + b + c = 15 have?)

Accepted Answer

Each split is a triple of non-negative whole numbers (a, b, c) with a + b + c = 15. Model it with 15 stars (tokens) and 2 bars separating the 3 piles. Every arrangement of the 15 + 2 = 17 symbols is one solution, so choose the 2 bar positions: \binom{15 + 3 - 1}{3 - 1} = \binom{17}{2} = \frac{17 	imes 16}{2} = 136. Takeaway. Counting non-negative solutions of x1 + \cdots + xk = n is stars and bars: \binom{n+k-1}{k-1}. Here \binom{17}{2} = 136.

Splitting fifteen tokens into three piles

Your answer

Discussion

Learn the concepts

Related questions