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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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. $$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .