3
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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