Problem:
Find the number of ways identical coins can be separated into three nonempty piles so that there are fewer coins in the first pile than in the second pile and fewer coins in the second pile than in the third pile.
Solution:
Assume that there are three distinct piles with coins in the first, coins in the second, and coins in the third. The answer is the number of solutions to , where , and are integers satisfying .
Without the restriction , the number of solutions in positive integers is the same as the number of solutions to in nonnegative integers, which by the sticks-and-stones technique with 63 stones and 2 sticks is .
The number of solutions where is the number of solutions in nonnegative integers of . This equation has one solution for each odd number from 0 to 63 , which gives 32 solutions. Similarly, there are 32 solutions where and 32 solutions where . In addition, there is 1 solution where . Altogether there are solutions where at least two of the variables are equal.
Therefore there are solutions where all three variables assume distinct values. The number of unordered solutions is then
OR
Note that there are ways to place coins into two piles with a different number of coins in each pile. Consider the size of the smallest pile among the three piles. If it has 1 coin in it, then removing a coin from each pile reduces the problem to the case of two piles with coins.
If all three piles have at least two coins, then removing a coin from each of them reduces the problem to the case with coins and three piles. Thus if is the number of ways to build three piles using coins, then for ,
Applying the recursion twice gives for :
This form has the advantage that the sum of the last two terms simplifies to . Thus
Repeated application of this last recursion yields
OR
The result is the number of positive integer solutions to with . By letting , , and , this is equivalent to counting solutions to with . Because , the count equals the number of lattice points in the triangle defined by , , and .
This triangle is formed by taking the rectangle given by and and cutting it in half along the diagonal. The total number of lattice points in the rectangle is , while the number of points along the diagonal is . Hence the total number of lattice points in this triangle is