Skip to main content
edited tags
Link
user9072
user9072
Source Link
Esben
  • 63
  • 3

Even more generalized Catalan numbers

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.