MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the number of ways to parenthesize $n$ elements using applications of operators of arbitrary arities larger than or equal to $2$? For example, for $n=3$, there are $3$ ways: $$ abc, a(bc),(ab)c $$ and for $n=4$ there are 11 ways: $$ abcd,\ ab(cd),\ a(bc)d,\ (ab)cd ,\ a(bcd), (abc)d,$$ $$ a(b(cd)),\ a((bc)d),\ (ab)(cd),\ (a(bc))d,\ ((ab)c)d $$ Note that, if we restrict the operators to have arity $2$ (i.e. binary operators), then the answer would be given by the Catalan number $C_{n-1}$. (More generally, if we restrict the operators to have arity $p$, the answer would be given by generalized Catalan numbers. So the point here is that the arity is arbitrary, corresponding to a situation where I can select between operators of arities 2,3,4,...

An aymptotic formula for $n\to\infty$ would also be highly appreciated.

share|cite|improve this question
up vote 5 down vote accepted

A little bit of programming and a look up in the OEIS tells me that this is the sequence A001003, the solution to Schroeder's second problem, see also Wikipedia.

According to the page in OEIS, the asymptotic form is $$ \frac{n^{-3/2}}{4}\sqrt{\frac{\sqrt{18}-4}{\pi}}(3+\sqrt{8})^n. $$

share|cite|improve this answer
The wikipedia is clickable in this notation: – Gottfried Helms May 24 '13 at 1:10
Just was I was looking for. Thank you! – Esben May 24 '13 at 7:03
By the way, if you take just the first four terms in the sequence (1,1,3,11) and put them into OEIS, the first suggestion (out of 191) that comes up is in fact the right answer. OEIS is incredibly useful for these types of questions. – Kirill May 24 '13 at 17:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.