How to derive a function that maps a list to its possible "bracketings"? Recursion?

Question

Let $[n] = \{m \in \mathbb{N}: m < n\}$. Suppose $\Sigma$ is a set and $\Sigma^*$ is the set of sequences on $\Sigma$. That is $\sigma \in \Sigma^*$ means there exists $n\in \mathbb{N}$ such that $\sigma:[n] \to \Sigma$, that is, $\sigma$ is a function from $[n]$ to $\Sigma$, i.e. and ordered sequence on $\Sigma$.

Suppose $\circ: \Sigma^2 \to \Sigma$ is binary operation. I would like to define the concept of all "parenthesizations" of a sequence $\Sigma^*$ of elements of $\Sigma$. Especially, I would like to define that behaves like the following. Suppose $a, b, c, d \in \Sigma$ and $[a, b, c, d] \in \Sigma^*$.

\begin{align*} \circ_*([a]) =& \{a\}\\ \circ_*([a, b]) =& \{a \circ b\}\\ \circ_*([a, b, c]) =& \{a \circ (b \circ c), (a \circ b) \circ c)\}\\ \circ_*([a, b, c, d]) =& \{a \circ (b \circ (c \circ d)), a \circ ((b\circ c) \circ d), (a\circ b) \circ (c \circ d), (a \circ (b \circ c)) \circ d, ((a\circ b) \circ c) \circ d\} \end{align*}

That is, $\circ_*$ should map the sequence $\sigma$ to all the "parenthesizations" of the elements of $\sigma$.

My question is how, rigourously, to define the function $\circ_*:\Sigma^* \to \mathcal{P}(\Sigma)?$

I can define it sort in a way I consider to be not 100% rigorously as follows. Suppose $\sigma \in \Sigma^*$.

• If $|\sigma| = 1$ then $\sigma = [a]$ for some $a\in \Sigma$. We define $\circ_*(\sigma) = \circ_*([a]) = \{a\}$.
• If $|\sigma| = n > 1$ then let \begin{align*} \circ_*(\sigma) = \{\tau \in \Sigma:&\text{There exists } i \in \mathbb{N} \text{ with } 1 \le i < n \text{ such that } \\ & \text{there exists } x \in \circ_*(\sigma[0:i]) \text{ and there exists } y \in \circ_*(\sigma[i:n])\\ & \text{ such that } \tau = x \circ y\} \end{align*} That is, $\circ_*(\sigma)$ is the collection of $\tau \in \Sigma$ which correspond to splitting the sequence $\sigma$ at some $i$, applying $\circ_*$ to the smaller sequences, and applying $\circ$ to all pairs of the resulting sets.

The reason this approach doesn't feel totally rigorous is it relies on using $\circ_*$ to define $\circ_*$. It requires us to know $\circ_*$ on shorter sequences $\sigma$ to determine $\circ_*$ on longer sequences. A similar approach involves defining separate functions $\circ_n$ depending on the length of $\sigma$. In this case $\circ_n$ depends on having $\circ_m$ defined for $m< n$ but I can't think how to define in a finite number of steps (that is not needing an independent definition for each $n \in \mathbb{N}$ relying on the earlier ones). Clearly some sort of recursion is needed for this definition but I can't seem to get it right.

I've tried two approaches but haven't been able to get them to work.

The first approach is to use structural recursion to define the function $\circ_*$. My understand of structural recursion is we have a set $U$ with a base subset $B$ and "generator" functions $\mathcal{F}$ where each $f\in \mathcal{F}$ maps an element of $U$ (or a tuple in $U^n$) to another element of $U$. If $C$ is the inductive closure of $B$ under the functions in $\mathcal{F}$ then we can apply a structural recursion theorem. If $S$ is a set and we have a (1) function $h_B: B \to S$, (2) a function $\tilde{f}:S^n \to S$ for each $f\in \mathcal{F}$ with $f:U^n \to U$, and (3) the functions $f\in \mathcal{F}$ satisfy some hypotheses to ensure the inductive closure is freely generated, then it is possibly to uniquely extend $h_B$ to a function $h:C\to S$ so that $h|_B = h_B$ and we have $h(f(c_0, \ldots, c_{n-1})) = \tilde{f}(h(c_0), \ldots, h(c_{n-1}))$. In simple examples this is how addition or the factorial functions can be defined.

I have trouble seeing how to apply structural recursion to prove the existence of the function $\circ_*$. I would think $\circ_*$ is the target recursive function $h$ which means $U = C = \Sigma^*$ and $S = \mathcal{P}(\Sigma)$ and clearly $B = \Sigma^1$, the length one sequences. But I can't really tell what the functions $f\in \mathcal{F}$ should be or the corresponding functions $\tilde{f}$. It seems like I want the function $f$ to be something like "appending one element of $\Sigma$ to the a list $\sigma \in \Sigma^*$. That is, something like $+_d([a, b, c]) = [a, b, c, d]$. But with this definition I would need one function $+_{\alpha}$ for each $\alpha \in \Sigma$ which feels like a lot of functions in $\mathcal{F}$. The corresponding functions $\tilde{f}$ are even more mysterious.

The other approach is to try to recursively generate the functions $\circ_n$ for $n\in \mathbb{N}$. We have $\circ_1([a]) = \{a\}$ which is easy enough. And then I can somehow define $\circ_n$ assuming $\circ_m$ for $1 \le m < n$ has been defined. The problem is I can't figure out how to put this into the framework of the recursion relation I've given above. Like I guess we would have $U=\mathbb{N}$ but $S$ would somehow be the set of all functions from $\Sigma^* \to \mathcal{P}(\Sigma)$? I guess we might denote this set $Z = \mathcal{P}(\Sigma)^{\Sigma^*}$? so we're trying to find a function $h$ that maps natural numbers $n$ to functions $\sigma_n \in Z$? Clearly $\mathcal{F} = \{+_1\}$ the add-by-one operation, but what is the corresponding function $\tilde{f}:Z \to Z$? I get tripped up because we would have $h(n) = \circ_n$ which is fine, but $h(n+1) = \circ_{n+1}$ and I know the definition of $\circ_{n+1}$ will rely on $\circ_m$ for all $m<n$, it won't only rely on $\circ_n$.

Apologies for such a long post and maybe a lack of clarity, just trying to get out all my thoughts so readers can see what I'm thinking. I'm open to any hints on any of these approaches, or, if there is another easier approach I would be very open to hearing that as well! Basically the question is how to, formally, use the recursion theorem to define the function $\circ_*$ I gave an example of above?

Answer 1

Let's try this.

Let $[n] = \{m \in \mathbb{N}: m < n\}$.

For any set $X$ define $X^n$ by

$$ X^n = \{f\in \mathcal{P}([n] \times X)| f: [n] \to X\} = [n]^X $$ That is $X^n$ is the set of all functions from $[n]$ to $X$. If $\mathbf{x} \in X^n$ then for $0 \le i < n$ we have $\mathbf{x}(i) = \mathbf{x}_i \in X$.

In the question we have the set $\Sigma$. An $n$-sequence on $\Sigma$ is an element $\sigma \in \Sigma^n$. We define $$ \Sigma^* = \bigcup \{z \in \mathcal{P}(\mathbb{N}\times X)| \exists n \in \mathbb{N}(n \ge 1 \text{ and }z = \Sigma^n)\} = \bigcup_{i=1}^n\Sigma^i $$

There is a function $\circ: \Sigma \to \Sigma$

We desire a function $\circ_*:\Sigma^* \to $ which satisfies

• If $\boldsymbol{\sigma} \in \Sigma^*$ with $|\boldsymbol{\sigma}|=1$ then $\circ_*(\boldsymbol{\sigma}) = \{\boldsymbol{\sigma}_0\}$
• If $\boldsymbol{\sigma} \in \Sigma^*$ with $|\boldsymbol{\sigma}|=n>1$ then \begin{align*} \circ_*(\boldsymbol{\sigma}) = \{\tau \in \Sigma^*|& \text{ There exists } i \in \mathbb{N} \text{ with } 1 \le i < n \text{ such that}\\ &\text{there exists } x \in \circ_*(\boldsymbol{\sigma}_{0:i}) \text{ and there exists } y \in \circ_*(\boldsymbol{\sigma}_{i:n})\\ & \text{such that } \tau = x \circ y\} \end{align*}

We will build this up using approximations to $\circ_*$ called $\circ_n$ for $n\in \mathbb{N}\setminus \{0\}$ on sets $\Sigma^{\le n} \subset \Sigma^*$.. Define $$ \Sigma^{\le n} = \bigcup \{z\in \mathcal{P}(\mathbb{N}\times X)| \exists i\in \mathbb{N}(1 \le i \le n \text{ and } z = \Sigma^i\} = \bigcup_{i=1}^n\Sigma^i $$

We will inductively prove the existence of functions $\circ_n: \Sigma^{\le n} \to \mathcal{P}(\Sigma)$ that all satisfy the same conditions as $\circ_*$, just on a restricted domain.

For $n=1$ it is clear that $\circ_1(\boldsymbol{\sigma}) = \{\boldsymbol{\sigma}_0\}$.

Now we consider the case $n>1$. The induction hypothesis is that such a function $\circ_n:\Sigma^{\le n} \to \mathcal{P}(\Sigma)$ exists and we must show that a function $\circ_{n+1}:\Sigma^{\le n+1} \to \mathcal{P}(\Sigma)$ exists. $\circ_{n+1}$ should be a total functional relation between $\Sigma^{\le n+1}$ and $\mathcal{P}(\Sigma)$ which means it is subset of $\Sigma^{\le n+1} \times \mathcal{P}(\Sigma)$. First we choose $\circ_{n+1}$ so that $\circ_n \subset \circ_{n+1}$. That is, for $\boldsymbol{\sigma}$ with $|\boldsymbol{\sigma}|\le n$ we have $\langle \boldsymbol{\sigma}, \circ_n(\boldsymbol{\sigma})\rangle \in \circ_{n+1}$. Now we need only figure out how to handle $|\boldsymbol{\sigma}| = n+1$. Well we simply define the target of $\boldsymbol{\sigma}$ to be exactly the set in $\mathcal{P}(\Sigma)$ to satisfy the condition on $\circ_*$. That is for $\boldsymbol{\sigma}$ with $|\boldsymbol{\sigma}|=n+1$ we define

\begin{align*} \circ_{n+1}(\boldsymbol{\sigma}) = \{\tau \in \Sigma^*|& \text{ There exists } i \in \mathbb{N} \text{ with } 1 \le i < n \text{ such that}\\ &\text{there exists } x \in \circ_n(\boldsymbol{\sigma}_{0:i}) \text{ and there exists } y \in \circ_n(\boldsymbol{\sigma}_{i:n})\\ & \text{such that } \tau = x \circ y\} \end{align*}

We've avoided circularity here by defining $\circ_{n+1}$ in terms of $\circ_n$ which exists by the induction hypothesis. We then know such a $\circ_n$ exists for each $n$ by induction. We could have been slightly more careful in the proof if we had first defined $\circ_{n+1}$ as a subset of $\Sigma^{\le n+1}\times \mathcal{P}(\Sigma)$ and proven that $\circ_{n+1}$ is total and functional but we leave that level of rigor out here.

We then have

$$ \circ_* = \bigcup \{f \in \mathcal{P}({\Sigma^*} \times \mathcal{P})|\text{There exists } n \in \mathbb{N} \text{ such that } f=\circ_n\} $$ $\circ_*$ is total because for any $\boldsymbol{\sigma}\in \Sigma^*$ with $|\boldsymbol{\sigma}| = n$ there is a $\circ_n$ we can use to calculate $\circ_*(\boldsymbol{\sigma})$ and $\circ_*$ is functional because for $m \le n$ we have that $\circ_m$ agrees with $\circ_n$ restricted to $\Sigma^{\le m}$.

Here I've proven the existence of a function $\circ_*$ by forming approximations to $\circ_*$ called $\circ_n$ on restricted domains. I have not used any recursion theorems, however, I think it's possible that this proof could be generalized into another type of recursion theorem (which are proved by induction on their domains anyways..). I'd appreciate any details or references about how to generalize this proof into a recursion theorem.

Answer 2

I don't know if this helps you because you seem to be interested in recursion, but there's a way to do this using gradings on monoids that doesn't require recursion. I'll expand a bit on what I mean with gradings and then construct your function. It's a bit verbose but it has the merit of being constructive. With an ordering on the alphabet, this could even be turned into an algorithm to compute your function.

---

Consider your alphabet $\Sigma$ and the alphabet $\Pi \overset{def}= \Sigma \cup \{(, )\}$ with the two extra symbols for each parenthesis. We consider $\Sigma^*$ to be the set of (finite) sequence of elements of $\Sigma$ called words (including the empty word) and we define $\Pi^*$ similarly. Together with the operation of concatenation, those sets form monoids, and $\Sigma^*$ is a submonoid of $\Pi^*$ because $\Sigma \subseteq \Pi$.

A grading on a monoid $M$ is just a morphism of monoids $g : M \to \mathbb Z$. We can write $M = \bigcup_{n \in \mathbb Z} M_n^g$ where $M_n^g \overset{def}= g^{-1}(n)$ is the set of elements of $g$-degree $n$, also called the $g$-graded component of degree $n$ of $M$. It's because $g$ is a morphism of monoids that for $m \in M_n^g$ and $m' \in M_{n'}^g$, we have $mm' \in M_{n+n'}^g$.

Of interest to us is a particular class of gradings. For a subset $\Gamma \subseteq \Sigma$, we get a morphism of monoids $\pi_{\Gamma}: \Sigma^* \to \Gamma^*$ given by taking a word $x = a_1 \cdots a_n \in \Sigma^*$ and removing the symbols $a_i$ belonging to $\Sigma \setminus \Gamma$, keeping those belonging to $\Gamma$ in the same order. Then, we consider the length grading $\ell : \Sigma^* \to \mathbb Z$ which just takes a word and returns the number of symbols in it (counting repetitions of course). We can compose morphisms of monoids, so for a given $\Gamma \subseteq \Sigma$, the composition $\ell_{\Gamma} \overset{def}= \ell \circ \pi_{\Gamma}$ is called the $\Gamma$-length grading; it counts the number of symbols appearing in a word that belong to $\Gamma$.

Note that gradings can be added and subtracted; that is because the map $\mathbb Z \to \mathbb Z$ multiplying by $-1$ is a morphism of abelian groups, so that the negative of a grading is also a grading (use composition).

The few gradings we will need to consider:

• For $\Gamma = \Sigma \subseteq \Pi$, the $\Sigma$-length grading on $\Pi^*$ determines the number of symbols in a word belonging to $\Sigma$. We denote it by $\gamma : \Pi^* \to \mathbb Z$.
• For $\Gamma = \Pi$, the $\Pi$-length grading on $\Pi^*$ is just the full word length $\ell : \Pi^* \to \mathbb Z$.
• For $\Gamma = \{(\}$, we get the left parenthesis grading $L$; similarly, we get the right parenthesis grading $R$ for $\Gamma = \{)\}$. These count the number of left (resp. right) parentheses in a word in $\Pi^*$.
• Let $b = b_1 \cdots b_n \in \Pi^*$ (where $b_1,\cdots,b_n \in \Pi$). For $m \ge 0$, the $m$-truncation of $b$, denoted by $[b]_m$, is just the word $b_1 \cdots b_m$ for $m < n$, and $b$ for $m \ge n$. To restrict our attention to words with bracketings of interest (using Dyck paths as an analogy), we need to consider words $b \in \Pi^*$ satisfying $L([b]_m) \ge R([b]_m)$ for $m \ge 0$ and $L(b) = R(b)$ (so that each right parenthesis can match with a left parenthesis coming before it). This can be reformulated with the grading $P \overset{def}= L - R$.

A word $b \in \Pi^*$ is called coherently bracketed if $P(b) = 0$ and $P([b]_m) \ge 0$ for all $m \ge 0$. Coherently bracketed words in $\Pi^*$ form a submonoid $\mathrm{CB}(\Sigma) \subseteq \Pi^*$. To see this, note that for $b,b' \in \Pi^*$ and $m \ge 0$, we have $$ [bb']_m = \begin{cases} [b]_m & \text{ if } m < \ell(b) \\ b[b']_{\ell(x) - m} & \text{ if } m \ge \ell(b). \end{cases} $$ Suppose $b,b'$ are coherently bracketed. Then $P(bb') = P(b) + P(b') = 0 + 0 = 0$. For $m \ge 0$, we'd have $$ P([bb']_m) = \begin{cases} P([b]_m) & \text{ if } m < \ell(b) \\ P(b) + P([b']_{\ell(x) - m}) & \text{ if } m \ge \ell(b). \end{cases} $$ which is non-negative in both cases. Since $\mathrm{CB}(\Sigma)$ is a submonoid, it also inherits all the gradings we put on $\Pi^*$ by composing a grading $g : \Pi^* \to \mathbb Z$ with the inclusion map $\mathrm{CB}(\Sigma) \subseteq \Pi^*$.

Now what we are interested in are not all coherently bracketed words in $\Pi^*$ because we want them to satisfy the following property: if "$(b_1 \cdots b_k)$" is a subword of $b \in \mathrm{CB}(\Sigma)$ with $b_1,\cdots,b_k \in \mathrm{CB}(\Sigma)$, then $k=2$ (so we can apply composition later to those subwords). We denote this property by (*).

Coherently bracketed words satisfying (*) determine a submonoid of $\mathrm{CB}(\Sigma)$ because if $x,y \in \Pi^*$ are coherently bracketed and the word $z$ given by "$(b_1 \cdots b_k)$" is a subword of the concatenation $xy$, we can consider the function $m \mapsto P([z]_m)$ which satisfies $P([z]_m) = 0$ if and only if $m = 0$ or $m \ge \ell(z)$; that's because the subwords $b_1, \cdots, b_k$ are coherently bracketed. So if we write $xy = vzw$ for some (possibly empty) words $v,w \in \Pi^*$, since $P(x) = 0$ and $P([z]_m) > 0$ for $0 < m < \ell(z)$, we deduce that $z$ is a subword of $x$ or $y$, and in both cases we deduce that $k=2$ since $x$ and $y$ satisfy (*), which means $xy$ does too. We denote this submonoid by $\mathrm{CB}_*(\Sigma)$.

So, if we want to consider all the bracketings of the word $a_1 \cdots a_n \in \Sigma^*$, what we want is the set of words $b \in \Pi^*$ such that

• the word $b$ has to be coherent, i.e. $P(b) = 0$ and $P([b]_m) \ge 0$ for all $m \ge 0$
• $L(b) = R(b) = \gamma(b)-2$
• $b$ satisfies (*), i.e. if "$(b_1 \cdots b_k)$" is a subword of $b$ with $b_1,\cdots,b_k \in \mathrm{CB}(\Sigma)$ and $k \ge 0$, then $k=2$.

Those are precisely the sets $\mathrm{CB}_*(\Sigma)_n^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-2}^{L}$; they contain all the bracketings of all the words in $\Sigma^*$ of $\gamma$-length $n$.

---

Now we go back to the question of determining the function $\Sigma^* \to \mathcal P(\Sigma)$ that you wanted. We are given a binary operation $\circ : \Sigma^2 \to \Sigma$. Given a word $x \in \Sigma^*$, first we want to have the set of all bracketings in $\mathrm{CB}_*(\Sigma)$ which when we strip the parentheses from them, give us $x$ back. Then we want to use those parentheses to determine the order in which we should perform the compositions with $\circ$.

Recall from earlier that since $\Sigma \subseteq \Pi$, we have a morphism of monoids $\pi_{\Sigma} : \Pi^* \to \Sigma^*$ that simply removes parentheses from words. We can restrict this morphism to $\mathrm{CB}_*(\Sigma)$ and get the morphism $\pi_{\mathrm{CB}_*} : \mathrm{CB}_*(\Sigma) \to \Sigma^*$ (which does the same thing: remove parentheses).

Let $x \in \Sigma^*$ with $\ell(x) \ge 3$. A bracketing of $x$ is a coherently bracketed word $b \in \mathrm{CB}_*(\Sigma)$ satisfying $\gamma(b) = \ell(x)$, $L(b) = R(b) = \gamma(b) - 2$ and $\pi_{\mathrm{CB}_*}(b) = x$ (in particular, $b$ satisfies (*)). Therefore, if we set $n \overset{def}= \ell(x)$, the set $$ B(x) \overset{def}= \pi_{\mathrm{CB}_*}^{-1}(x) \cap \mathrm{CB}_*(\Sigma)_n^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-2}^L $$ consists of all the bracketings of $x$. If $0 < \ell(x) < 3$, we set $B(x) = \{x\}$, and if $\ell(x) = 0$, we set $B(x) = \varnothing$.

Let $b$ be a bracketing of $x \in \Sigma^*$ with $\gamma(b) \ge 3$. We work iteratively with two steps: we first find a canonical choice of sub-word of $b$ of the form "$(a_1a_2)$" with $a_1,a_2 \in \Sigma$, and then we use that sub-word and replace it by $a_1 \circ a_2$. This new word is now a word in $\Sigma^*$ of length $\ell(x) - 1$, so we can iteratively repeat this process until $\ell(x) = 2$, in which case we don't need the brackets and just compose to get an element of $\Sigma$.

Step 1: There exists a sub-word of $b$ of the form "$(a_1a_2)$" for some $a_1,a_2 \in \Sigma$. To see this, consider the function $m \mapsto P([b]_m)$. Since it takes only finitely many values, it attains a maximal value, say $\alpha$. Suppose $m_0$ satisfies $P([b]_{m_0}) = \alpha$. Because $m \mapsto P([b]_m)$ only varies in increments of $1$, the values taken by that function surrounding $m_0$ must look like $$ \cdots, P([b]_{m_0-1}), P([b]_{m_0}), P([b]_{m_0+1}), \cdots, P([b]_{m_0+k}), P([b]_{m_0+k+1}) \cdots \qquad = \qquad \cdots, \alpha-1, \alpha, \alpha, \cdots, \alpha, \alpha-1, \cdots. $$ with the value $\alpha$ repeated $k$ times for some $k \ge 0$ ($k=0$ would make the sequence look like $\cdots, \alpha-1, \alpha, \alpha-1, \cdots$). The first occurence of $\alpha$ as the value of $P([b]_{m_0})$ implies that $[b]_{m_0}$ ends with a left parenthesis, and the occurence of $\alpha-1$ after the sequence of $\alpha$'s implies that $[b]_m$ ends in "$(a_1 \cdots a_k)$" with $k \ge 0$ and $a_i \in \Sigma$ for $i=1,\cdots,k$. Since $b$ satisfies (*), this means $k=2$ and "$(a_1a_2)$" is a subword of $b$.

Step 2: Let $x'$ be the word $x$ where the subword $a_1a_2$ is replaced by the composition $a_1 \circ a_2$. Also, let $b'$ be the word $b$ where the subword "$(a_1a_2)$" is replaced by the single symbol $a_1 \circ a_2 \in \Sigma$. We claim that $b'$ is a bracketing of $x'$.

It is clear that $b'$ is coherently bracketed, since the values $P([b']_m)$ taken are also values taken by $P([b]_m)$, so they are non-negative. Also, $P(b') = P(b) = 0$, and $L(b') = L(b) - 1 = \gamma(b) - 3 = \gamma(b') - 2$ (and similarly for $R(b')$).

As for the property (*) of $b'$, if "$(c_1 \cdots c_k)$" with $c_1,\cdots,c_k \in \mathrm{CB}(\Sigma)$ is a subword of $b'$, then either $a_1 \circ a_2$ is not involved and this is just a subword of $b$ (so that $k=2$) or $a_1 \circ a_2$ appears as a subword of one of the $c_i$'s. But then replacing $a_1 \circ a_2$ by "$(a_1 a_2)$" in that $c_i$ still keeps it coherently bracketed, and so $k=2$ because $b$ satisfies (*).

By taking the first available instance of a subword of the form "$(a_1a_2)$" in $b$ (first in the sense that you read $b$ from left to right), for any $n \ge 3$, we produced a function $$ f_n : \mathrm{CB}_*(\Sigma)_n^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-2}^L \to \mathrm{CB}_*(\Sigma)_{n-1}^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-3}^L $$ which sends a coherently bracketed word $b$ with $\gamma(b) = n$ and $L(b) = n-2$ satisfying (*) to $f_n(b) \overset{def}= b'$, and $\gamma(b') = n-1$ and $L(b') = n-3$. Let $$ \mathrm B(\Sigma) = (\Sigma^*)_1^{\ell} \cup (\Sigma^*)_2^{\ell} \cup \left( \bigcup_{n \ge 3} \mathrm{CB}_*(\Sigma)_n^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-2}^L \right). $$ Also, write $\mathrm B(\Sigma)_1 \overset{def}= (\Sigma^*)_1^{\ell} = \Sigma$ (words of length one are just the alphabet), then $\mathrm B(\Sigma)_2 \overset{def}= (\Sigma^*)_2^{\ell}$ (the words of length 2), and finally $\mathrm B(\Sigma)_n \overset{def}= \mathrm{CB}_*(\Sigma)_n^{\gamma} \cap \mathrm{CB}_*(\Sigma)_{n-2}^L$ for $n \ge 3$ (the bracketings of $n \ge 3$ symbols). By construction, we have $\mathrm B(\Sigma) = \bigcup_{n \ge 1} \mathrm B(\Sigma)_n$, and the subsets $\mathrm B(\Sigma)_n$ are all pairwise disjoint subsets of $\Pi^*$, so they partition $\mathrm B(\Sigma)$.

We define $f : \mathrm B(\Sigma) \to \mathrm B(\Sigma)$ as follows: for $n=1$ and $x \in \mathrm B(\Sigma)_1$, we set $f(x) = x$. For $n=2$ and $x \in \mathrm B(\Sigma)_2$, we have $x = a_1a_2$ for some $a_1,a_2 \in \Sigma$, and we let $f(a_1a_2) = a_1 \circ a_2$. For $n \ge 3$, we set $f(x) = f_n(x)$ where $n = \ell(x)$.

Putting all the pieces together: suppose $x \in \Sigma^*$. Then $B(x)$ contains all its bracketings, and $f^{\ell(x)-1}(B(x))$ (which is the set of all elements of $B(x)$ on which we apply the function $f$, $\ell(x) - 1$ times) is the composition of all those bracketings. So I would define the map as $$ \Lambda : \Sigma^* \to \mathcal P(\Sigma), \qquad x \mapsto \begin{cases} \varnothing & \text{ if } x \text{ is the empty word } \\ f^{\ell(x) - 1}(x) & \text{ otherwise.} \end{cases} $$ Hope that helps,