# Using your Head is Permitted

## November 2013 solution

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

*f*(*n*)=(2*n*)!/(*n*! 2^{n}).
This can be written using the double-factorial notation:

*f*(*n*)=(2*n*-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:

- Option 1: "()()".
- Option 2: "(())".
- Option 3: "(())".

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

1*3*...*(2*n*-1) = (2*n*)!/(*n*! 2^{n}).
To show that this value equals *f*(*n*), we prove three claims.

- All possible arrangements can be produced by this procedure.
- No
*im*possible arrangement can be produced by this procedure.
- 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