Is there a closed-form formula for this function from positive integers to positive integers?

Question

Suppose we are given $n$ letters, $n$ a positive integer. We are also given a binary operation $+$. I want to know how many ways we can group these letters with parentheses. For example, if $n=2$, then there are two groupings, namely $(x+y)$ and $(y+x)$. Also, if $n=3$, there are twelve groupings, namely $((x+y)+z)$, $(x+(y+z))$, $((y+x)+z)$, $(y+(x+z))$, etc. Is there a known closed-form formula for this function? Also, is there an OEIS entry for this sequence?

Answer 1

Yes. If we think of the parse tree of the expression, then the number of expressions where we ignore the nature of the variables is the number of full binary trees with $n-1$ non-terminal nodes (as that gives you $n$ terminals for the $n$ variables), and the closed formula for that is the Catalan number $\frac{(2(n-1))!}{(n)!(n-1)!}$. Now multiply by the number of ways you can distribute the $n$ different variables (which is $n!$), and you get the formula you are looking for:

$$\frac{(2(n-1))!}{(n-1)!}$$