Let be an integer. We are given a balance and weights of weight . We are to place each of the weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.

Solution:

I claim that the answer is Let denote the number of ways for a set . It is clear that and I will show that which will imply the desired result.

The key observation will be that placing the weight of on either pan can never make the right pan heavier than the left pan unless it is the first weight placed on the balance. So there is way to place it on your "first move" and ways to place it on all other moves. Therefore you can place the weight of in ways. The other weights can clearly be placed now in ways so as desired.