Using your Head is Permitted

November 2013 solution

A closed-form solution to this month's problem is

f(n)=(2n)!/(n! 2n).

This can be written using the double-factorial notation:

f(n)=(2n-1)!!.

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:

Continue recursively, adding each pair in turn. The i'th parentheses pair will be laid out in one of 2i-1 possible positions. Hence, the total number of possibilities for n pairs is

1*3*...*(2n-1) = (2n)!/(n! 2n).

To show that this value equals f(n), we prove three claims.

  1. All possible arrangements can be produced by this procedure.
  2. No impossible arrangement can be produced by this procedure.
  3. The number of duplications of any particular arrangement equals exactly the value of the arrangement.
The first of these claims is trivial. Given any legal arrangement of n pairs of parentheses, the left-most character must be "(". Take it and its paired ")", and assume that these were generated on the n'th round. Removing them, we are left with a legal arrangement of n-1 pairs. By induction, this arrangement of n-1 pairs can be generated in the first n-1 rounds.

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.

Q.E.D.

Back to riddle

Back to main page