Using your Head is Permitted

November 2013 riddle

Consider a set of n pairs of parentheses, arranged in some legal way (possibly concatenated to each other). For example,


is an example of such an arrangement, with n=4.

Each pair has a nesting level. Consider the value of the entire arrangement to be the product of the nesting levels. In our example, the value is 3*2*2*1=12.

Let f(n) be the sum of the values of all possible arrangements of n pairs of parentheses.

This month's riddle: find, with proof, a closed-form expression for f(n).

List of solvers:

Yuping Luo (6 November 17:09)
Dan Dima (7 November 05:38)
Naftali Peles (12 November 17:35)
Wenqi Zhang (16 November 11:38)
Radu-Alexandru Todor (16 November 13:00)
Daniel Bitin (25 November 08:31)
Andreas Stiller (25 November 23:35)
Lorenz Reichel (27 November 23:32)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page