I want to find the number of ways to product $n$ terms of a monoid in specific order.
Let $G$ be a monoid, and $x_i$'s are elements of $G$.
We see that
$x_1$
$x_1 x_2$
$(x_1 x_2) x_3, ~~~ x_1 (x_2 x_3)$
$((x_1 x_2) x_3)x_4, ~~~ (x_1(x_2x_3))x_4, ~~~ (x_1x_2)(x_3x_4), ~~~ x_1((x_2x_3)x_4), ~~~ x_1(x_2(x_3x_4))$
$\ldots$
In this way, let $a_n$ be a number of a way to product $x_1, \ldots, x_n$ with order-preserving.
Then $a_1 =1$, $a_2 = 1$, $a_3 = 2$.
And we find that $a_4 = a_1 a_3 + a_2 a_2 + a_3 a_1$.
Similarly, the general term $a_n$ is recursively obtained by
$$a_n = a_1 a_{n-1} + a_2 a_{n-2} + \ldots + a_{n-2} a_2 + a_{n-1} a_1 = \sum\limits_{i=1}^{n-1} a_i a_{n-i}.$$
The initial value is $a_1 =1$ and $a_2 = 2$.
How to find the general term explicitly?
