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.


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. $$

  • $\begingroup$ The wikipedia is clickable in this notation: en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number $\endgroup$ – Gottfried Helms May 24 '13 at 1:10
  • $\begingroup$ Just was I was looking for. Thank you! $\endgroup$ – Esben May 24 '13 at 7:03
  • $\begingroup$ 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. $\endgroup$ – Kirill May 24 '13 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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