This can be written using the double-factorial notation:
As for the proof, this month there were as many different solutions as there were solvers, with solutions ranging from highly technical to extremely elegant.
The (most-elegant) solution given here comes from Itsik Horovitz. (Thanks!)
Start with one pair of parentheses "()". Then, to create an arrangement with two pairs, add an opening parenthesis at the left of the string and a closing one at each of the 3 possible locations:
To show that this value equals f(n), we prove three claims.
The second claim is likewise straightforward: a legal arrangement of parentheses is one in which every prefix of the parentheses string has at least as many opening parentheses as closing parentheses. Our procedure for adding a pair of parentheses clearly does not upset this invariant.
To prove the third claim, let us calculate the number of duplications for each combination in the following manner.
Consider the left-most of the closing parentheses (")"). This closing parenthesis could have originated together with any one of the opening parentheses before it. The number of these also happens to be its nesting level.
If we remove this closing parenthesis together with its partner, this does not change the nesting level of any of the other closing parentheses. We can therefore repeat the process recursively, and by induction reach the conclusion that the total is the product of all nesting levels, and hence the value of the arrangement.
Back to riddle
Back to main page