In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}\_{r\_{\text{min}}} = \{\epsilon,(),(()),()(()),((())), \ldots\}$. So what exactly is $\mathcal{D}\_{r\_{\text{min}}}$? It's the set of *Dyck natural numbers*, i.e., the set of recursive prime factorizations $\{\gamma'\_{\mathbb{N}\_{r}}(n) \mid n \in \mathbb{N}\}$, where $\gamma'\_{\mathbb{N}\_{r}}$ is given by Definition 3 below (Definitions 1 and 2 introduce notation for use in Definition 3):


**Definition 1.** The symbol $\frown$ is the string concatenation operator; $a \frown b$ denotes the concatenation of $a$ and $b$. The concatenation of $a$ and $b$ may also be written in customary fashion as $ab$, provided that doing so does not incur ambiguity.


**Definition 2.** Let $j,k \in \mathbb{N}\_{+}$. Then we shall understand $\bigoplus\_{i=j}^{k}s\_{i}$ to denote the string concatenation $s\_{j} \ldots s\_{k}$ if $j \le k$, otherwise the empty string $\epsilon$.


**Definition 3.** Let $\Sigma^\*$ be the Kleene closure of the set $\{(,)\}$. Then the *standard nonsurjective recursive prime factorization natural transcription function*, denoted by $\gamma'\_{\mathbb{N}\_{r}}$, is given by $\gamma'\_{\mathbb{N}\_{r}}: \mathbb{N} \rightarrow \Sigma^\*$, where


* For $n = 0$, $\gamma'\_{\mathbb{N}\_{r}}(n)$ is the empty string $\epsilon$.
* For $n = 1$, $\gamma'\_{\mathbb{N}\_{r}}(n)$ is the string $()$.
* For $n > 1$, let $p\_{i}$ be the $i$th prime number, let $p\_{m}$ be the greatest prime factor of $n$, and let $a = (a\_{1}, \ldots, a\_{m})$ be the integer sequence satisfying
\begin{equation}
n = \prod\_{i=1}^{m}p\_{i}^{a\_{i}}.
\end{equation}
Then
\begin{equation}
\gamma'\_{\mathbb{N}\_{r}}(n) = \bigoplus\_{i=1}^{m}(\;'('\frown \gamma'\_{\mathbb{N}\_{r}}(a\_{i}) \frown ')'\;).
\end{equation}


Note: It is $\gamma'\_{\mathbb{N}\_{r}}$ rather than $\gamma\_{\mathbb{N}\_{r}}$ because I restrict its codomain to yield the bijection $\gamma\_{\mathbb{N}\_{r}}$ (which I call the *standard RPF natural spelling function*; I do this so that my spelling function will have an inverse, allowing me to map from $\mathcal{D}\_{r\_{\text{min}}}$ to $N$). The subscript $\mathbb{N}$ tells us that the function maps natural numbers to Dyck words, in order to distinguish the function from another one that maps *rationals* to Dyck words. Finally, the subscript $r$ indicates that it involves the right-ascending sequence of prime numbers $(2,3,5,7, \ldots)$, rather than some other prime permutation such as $(\ldots,7,5,3,2)$ or $(3,2,7,5,\ldots)$.


Now let $S\_{k}$ be the subset of $\{0,1,2,3,\ldots\}$ such that every member of $S\_{k}$ is represented by a Dyck natural number of semilength $k$. Then


$S\_{0} = \{0\}$


$S\_{1} = \{1\}$


$S\_{2} = \{2\}$


$S\_{3} = \{3,4\}$


$S\_{4} = \{5,6,8,9,16\}$


$S\_{5} = \{7,10,12,15,18,25,27,32,64,81,256,512,65536\}$


Notice that the largest members in sets $S\_{2}$ through $S\_{5}$ can be expressed as $2$, $2^{2}$, $2^{2^2}$ and $2^{2^{2^{2^2}}}$, respectively. If the pattern holds, then the greatest number in $S\_{6}$ is equal to $2^{65536}$; thus I will not try to list the members in further $S\_{k}$. But we have enough information to describe the sequence as $(1,1,1,2,5,13, \ldots)$, and there are several candidates in the Online Encyclopedia of Integer Sequences. So what's the sequence?


**IMPORTANT NOTE:** $\mathcal{D}\_{r\_{\text{min}}}$ has an alternative nonnumerical definition (see Theorem 2.7 in Section 2.8 of arXiv:2102.02777):


**Definition 4.** Let $\mathcal{D}$ denote the Dyck language. The *standard minimal RPF language*, denoted by $\mathcal{D}\_{r\_{\text{min}}}$, is the set
\begin{equation}
\{d \in \mathcal{D} \mid (\;{'})()){'} \text{ is not a substring of } d\;)\;\wedge\;(\;{'})(){'} \text{ is not a suffix of } d\;) \}.
\end{equation}


Thus my question can be answered by providing a formula for the number of Dyck words of semilength $k$ not containing the substring ${)())}$ or the suffix ${)()}$, where $k \ge 0$.


Thank you...



What is the cardinality of the set of Dyck natural numbers of semilength $k$?
Let $N\_n$ be the number of words of semilength $n$ in
$$\{d \in \mathcal{D} \mid (\;{'})()){'} \text{ is not a substring of } d\;)\;\wedge\;(\;{'})(){'} \text{ is not a suffix of } d\;) \}.$$


Then $N\_0 = N\_1 = 1$, and similarly to Catalan numbers for $n\geq 2$, we have a recurrence:
\begin{split}
N\_n &= \sum\_{i=0\atop i\ne n-2}^{n-1} N\_i N\_{n-1-i} \\
&= \sum\_{i=0}^{n-1} N\_i N\_{n-1-i} - N\_{n-2}
\end{split}
It follows that the generating function $F(x):=\sum\_{n\geq 0} N\_nx^n$ satisfies the identity:
$$F(x) = 1 + xF(x)^2 - x^2F(x),$$
implying that
$$F(x) = \frac{1+x^2 - \sqrt{1-4x+2x^2+x^4}}{2x}.$$


In OEIS, your sequence is [A082582](https://oeis.org/A082582), which also gives the number of Dyck words of semilength $n$ with no `(())`. It is also the shifted [A086581](https://oeis.org/A086581), i.e., the number of Dyck words of semilength $n-1$ with no `))((`. It is also almost [A025242](https://oeis.org/A025242).


