the bracket partition function ? $3 = 1 + 1 + 1 = 1 + 2 = 1 + (1 + 1) $

Question

I want to know in how many ways we can write a positive integer by using strict positive integers, addition and brackets. The order of addition does not matter.

For instance

$$3 = 1 + 1 + 1 = 1 + 2 = 1 + (1 + 1) $$

invalid expression are brackets over the whole such as $(1+1+1),(3)$ and nonsensical bracket use such as $1+1+(1)$ or $1+() + 2$ not closing the brackets.

So we can write 3 in 4 ways.

Let $M(n)$ be the number of ways we can write $n$ like that.

This function $M(n)$ is clearly an analogue to the partition function, and it grows faster.

But how fast does this function grow ?

What is known about it ?

I tried to find useful recurrence equations and generating functions but failed.

---

Similar question for $T(n)$ which counts the number of ways but where the order matters for distinct parts. So here $1+1+1$ counts as one way , but $1 + 2$ and $2+1$ count as 2 ways.

edit

See also :

https://mathworld.wolfram.com/Bracketing.html

https://mathworld.wolfram.com/SuperCatalanNumber.html

https://en.wikipedia.org/wiki/Partition_function_(mathematics)

---

Answer 1

For the first question, this is equivalent to first choosing an integer partition with $k$ parts, for some $k\in \{2,\dots,n\}$, and then choosing a way to parenthesize a sum of $k$ numbers. There are $C_{k-1}=\frac1k\binom{2(k-1)}{k-1}$ ways to parenthesize a sum of $k$ numbers. If you let $p(n,k)$ be the number of partitions with exactly $k$ parts, this means $$M(n)=\sum_{k=1}^n p(n,k)C_{k-1}.$$ I do not know if this is the simplest form of the answer, but I suspect it is.

For $T(n)$, we need to replace $p(n,k)$ with the number of compositions of $n$ with $k$ parts, which is well known to be $\binom{n-1}{k-1}$. That is, $$ T(n)=\sum_{k=1}^n \binom{n-1}{k-1}C_{k-1} $$ This is the simplest form for $T(n)$, which I have confirmed using Zeilberger's algorithm and Petkovšek's algorithm (as discussed in the book A = B).

Now that you have formulae for these sequences, you can compute some initial terms, and see if either is in OEIS to get more information.