What is the cardinality of the set of Dyck natural numbers of semilength $k$?

Question

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...

Answer 1

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, which also gives the number of Dyck words of semilength $n$ with no (()). It is also the shifted A086581, i.e., the number of Dyck words of semilength $n-1$ with no ))((. It is also almost A025242.