Catalan Numbers and Generating Uniform Balanced Bracket Sequences

This was written jointly by errorgorn and me and published on errorgorn’s blog, and the original post is here. You can also check out his personal blog here.

Hi everyone! Today nor sir and I would like to talk about generating uniform bracket sequences. Over the past few years when preparing test cases, I have had to generate a uniform bracket sequence a few times. Unfortunately I could not figure out how, so I would like to write a post about this now. Hopefully this post would be useful to future problem setters :) Scroll down to the end of the post to copy our generators.

First, let’s define some things. A bracket sequence is a string with \(n\) \(\texttt{(}\) s and \(n\) \(\texttt{)}\) s. A balanced brackets sequence is a bracket sequence with the additional constraint that it becomes a valid arithmetic expression when we add some \(\texttt{1}\) s and \(\texttt{+}\) s. Let \(p\) be the prefix sum array of a bracket sequence (we assign \(1\) to \(\texttt{(}\) and \(-1\) to \(\texttt{)}\) and take the prefix sum). For example, if our bracket sequence is \(\texttt{())()((())}\), then \(p=[1,0,-1,0,-1,0,1,2,1,0]\).

An alternate way to think about the prefix sum is to imagine the bracket sequence as a sequence of increasing and decreasing lines.

We can see that the necessary and sufficient for a bracket sequence to be balanced is that all elements of the prefix sum is non-negative.

Let’s define the badness of a bracket sequence as the number of lines in the above diagram that is below the \(0\)-line. So, the badness of our bracket sequence is \(4\).

Let’s call a bracket sequence irreducible if the line touches the \(0\)-line exactly twice (once at the start and at the end). So, \(\texttt{(())}\) and \(\texttt{))()((}\) are both irreducible but not \(\texttt{()()}\). It is natural to also define a irreducible decomposition of a bracket sequence. \(\texttt{())()((())}\) gets decomposed into \(\texttt{()}\),\(\texttt{)(}\),\(\texttt{)(}\),\(\texttt{(())}\).

Now, we want to note that all irreducible bracket sequences are either balanced or are some sort of “inverse” of a balanced bracket sequences. By inverse, we can either reverse the entire string or flip every bracket in the string. Please note that these are different.

For example, \(\texttt{)))(()((}\) can be turned into \(\texttt{((())())}\) by flipping every bracket or \(\texttt{(()(()))}\) by reversing the substring.

Firstly, let’s start with finding a recursive formula for the Catalan numbers. One of the basic recurrences when dealing with bracket sequences is to decompose them into the form of \(\texttt{(}X\texttt{)}Y\), where \(X\) and \(Y\) are both valid bracket sequences (they might be empty). This decomposition is actually unique since \(\texttt{(}X\texttt{)}\) can only be our first term in our irreducible decomposition (for us competitive programmers, think of it as dp where our transition is removing the first irreducible substring). We immediately have the recurrence \(C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}\) for \(n > 0\) and a base case of \(C_0=1\) for \(n=0\). After some manipulation with formal power series \([1,2 \text{ example } 2.3.3]\), you can find that we get the familiar \(C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{1}{2n+1} \binom{2n+1}{n}\).

Mapping 1

Let’s take a look at \(C_n = \frac{1}{2n+1} \binom{2n+1}{n}\) first. What other sequence can we get the \(\binom{2n+1}{n}\) term from? Well, the number of binary strings with \(n\) \(\texttt{(}\) s and \(n+1\) \(\texttt{)}\) s. And nicely enough, \(2n+1\) is the length of said binary string. Let’s define the equivalence class \(\sim _R\) where \(s\sim_Rt\) when \(s\) is a cyclic shift of \(t\). Generally for binary strings, it is not so easy to count the number of elements in someone’s equivalence class when we define it this way. But since \(\gcd(2n+1,n)=1\) here, all cyclic shifts of a string are distinct and there are exactly \(2n+1\) strings in any equivalence class. We are almost at a bijection to Catalan numbers already! We just need to show that there is a bijection between equivalence classes and balanced bracket sequences.

• Lemma

  Given a string of \(n\) \(\texttt{(}\)s and \(n+1\) \(\texttt{)}\)s, there exists exactly \(1\) cyclic shift where the first \(2n\) elements is a valid bracket sequence.

  As an example, consider the bracket sequence \(\texttt{)())(()}\). The only cyclic shift that gives us a prefix sum with our condition is \(\texttt{(())())}\).

  The proof of this is not too hard and you should prove it yourself, but for completeness, I will put it here.

  proof

  Let us define the special index \(s_p\) as the index (\(0\)-indexed) of the leftmost minimum value of the prefix sum. For example, \(\texttt{)())(()}\) gives us \(p=[-1,0,-1,-2,-1,0,-1]\), \(s_p=3\). By definition the \(s_p\) is the unique index such that \(p_i > p_{s_p}\) if \(i<s_p\) and \(p_{s_p} \leq p_i\) if \(s_p<i\).

  Claim: when we perform a right rotation on the string, the special index will be updated like \(s_p \gets (s_p+1) \% (2n+1)\). Loosely, the special index shifts along with the string.

  Let us consider that currently our prefix sum is \(p=[p_1,p_2,\ldots,p_k]\). After a single right rotation, it will become \(p’=[0+(p_k-p_{k-1}),p_1+(p_k-p_{k-1}),p_2+(p_k-p_{k-1}),\ldots,p_{k-1}+(p_k-p_{k-1})]\). That is, we append \(0\) to the beginning of \(p\), delete the last element of \(p\), then add \(p_k-p_{k-1}\) to all elements.

  We want to show that \(s_{p’}= (s_p+1) \% (2n+1)\). We will split into two cases.

  Note that \(p_k\) is \(-1\), since there are \(n\) \(\texttt{(}\)s and \(n+1\) \(\texttt{)}\)s. Furthermore, we can more easily consider \(p’=[0,p_1,p_2,\ldots,p_{k-1}]\) since adding a constant all elements of \(p’\) does not change \(s_{p’}\).

  • Case 1

    Suppose that \(s_p < 2n\), then \(s_{p’} = s_{p}+1\). From our assumption that \(s_p\) is the special index of \(p\), we already have that \(p’_i > p’_{s_p+1}\) if \(1 \leq i<s_{p}+1\) and \(p_{s_p+1} \leq p_i\) if \(s_p+1<i\). It only remains to prove that \(p’_0 > p’_{s_p+1}\).

    Since \(p_k=-1\), it must be true that \(p_{s_p} \leq -1\). We obtain \(p’_0=0>-1\geq p_{s_p}\). Therefore, \(p’_0 > p’_{s_p+1}\) and \(s_{p’}=s_p+1\) is the special index of \(p’\).

  • Case 2

    Suppose that \(s_p = 2n\). We only have to prove that all elements of \(p’\) are non-negative to claim that \(s_{p’}=0\). This is easy by contradiction. Suppose that \(p’_j < 0\). Then it is impossible that \(0 > p_{j-1} > p_{2n}=-1\). \(\blacksquare\)

    In fact, our claim is a modified version of cycle lemma where we have \(m=n+1\) and \(k=1\) (see, for instance, \([3]\) for two nice proofs – one by arranging the sequence on a circle and removing certain segments, and the other using an idea similar to the prefix sum idea presented above).

    Now, let us rotate the string until \(s_p=2n\). By our above claim, there is a unique position that satisfies this. since there are \(n\) \(\texttt{(}\)s and \(n+1\) \(\texttt{)}\)s, we have \(p_{2n}=p_{s_p}=-1\). So, \(p_i \geq 0\) for all \(0 \leq i < 2n\). That is, the first \(2n\) characters of the string is now a valid bracket sequence.

  We can see that in each equivalence class, there is exactly a single element whose first \(2n\) elements are a balanced bracket sequence. Let this be the representative of the equivalence class. We can obtain balanced bracket sequences from representatives by removing the last character and vice versa by appending a \(\texttt{)}\). Therefore, there is a bijection between the equivalence classes and

  There is a interesting problem which is related to this \([4]\) (in Chinese).

  translation

  This translation is extremely abridged because I do not want to translate some stupid story line about the main characters from Chū-2 playing Yu-Gi-Oh.

  There are \(m\) cards. An array \(a\) of length \(n \leq m\) describes these cards where \(m = \sum\limits_{i=1}^n a_i\). If \(i \leq n\), then the \(i\)-th card has the string \(\underbrace{\texttt{((}\ldots\texttt{(}}_{a_i-1 \ \text{times}}\). Otherwise, the \(i\)-th card has the string \(\texttt{)}\). Out of all \(m!\) ways to order the cards, find the number of valid orderings such that the cards, when read left to right, forms a valid bracket sequence.

  Constraints:

  • \(1 \leq n \leq 40\)
  • \(1 \leq a_i \leq 10^5\)
  solution

  Let’s do the same set-up as earlier by adding an extra card that has the string \()\). Then we define the equivalence class in the same way, except now each equivalence class only has \(m+1\) elements (well, we only have \(m+1\) cards). I claim that each equivalence class still has exactly \(1\) valid rotation.

  Let’s pretend that the cards don’t exist for a while and we are just dealing with strings of length \(2(n-m)+1\). We know that out of the \(2(n-m)+1\) rotations, exactly one is valid, so our only concern is that this valid rotation is not present when we add on constraint about rotation with the “barriers” of the cards. But this will never happen because the string will be of this form \(\texttt{(}X\texttt{))}\).

  It is not too hard to show that each of the \(3\) brackets belong to different cards due to the types of string that can be written on each cards. That is, we first have a valid rotation out of the possible \(m+1\) rotations when accounting for the “barriers” of the cards, and the last character corresponds to a single card, so we can simply remove it.

  Let’s count first the number of ways with the addition of the extra card (remember that even if two cards have the same string, they are distinguishable). We have two types of cards — \(\texttt{((}\ldots\texttt{(}\) and \(\texttt{)}\). We have \(n\) cards of the first type and \(m-n+1\) cards of the second types. Overall, we have \(\frac{1}{m+1} (m+1)! = m!\) valid ways to arrange them.

  However, we have overcounted as we added our extra card. But no problems, it is easy to see that we counted each unique sequence \(m-n+1\) times since each card of type \()\) has equal probability to be the last card that is removed. So, just divide our answer by \(m-n+1\) and we get the answer of \(\frac{m!}{m-n+1}\).

Mapping 2

Thank you nor sir for writing this part and independently discovering it.

The mapping mentioned here was, unfortunately, already present in literature \([5]\) after we checked, and my old proof was quite similar to the one mentioned in the paper. It used the Chung-Feller theorem, which says that the badness of bracket sequences is uniformly distributed (i.e., there are an equal number of strings for each value of badness), and then showed that the mapping was in fact a bijection from the set of strings of a fixed badness to the set of balanced bracket sequences.

However, I came up with a much simpler proof which we will present below along with the intuition behind the construction (we could not find this proof anywhere, so if anyone finds a reference, please let us know in the comments).

The main idea behind what we will do below is the identity \(C_n = \frac{1}{n + 1} \binom{2n}{n}\). We try to construct a balanced bracket sequence from a bracket sequence with \(n\) opening brackets and \(n\) closing brackets, and then try to show that this construction is in fact an \(n + 1\) to \(1\) mapping from \(S_n\) (the set of bracket sequences with \(n\) opening brackets and \(n\) closing brackets) to \(S^*_n\) (the set of balanced bracket sequences of length \(2n\)).

The first idea is to note that, as mentioned earlier, if a string \(S = AB\), where \(A\) is the irreducible prefix of \(S\), then we can make \(A\) an irreducible balanced bracket sequence by either flipping all brackets of \(A\) (which corresponds to flipping the corresponding diagram in the \(x\)-axis) or by reversing the string \(A\) (which corresponds to rotating the diagram \(180^\circ\)).

The first attempt at finding a mapping was to do this: set \(f(S) = A’f(B)\), where \(A’\) is the string obtained by flipping all brackets in \(A\) (or just reversing \(A\)). However, this will not give us a uniformly random way of constructing balanced bracket sequences, since \(\texttt{((()))}\) is the image of \(2\) strings under this mapping, and \(\texttt{()()()}\) is the image of \(8\) strings under this mapping.

So here was the crucial idea: we try to offset this asymmetry by modifying how we handle the case when \(A \ne A’\). In this case, \(A =\; \texttt{)}C\texttt{(}\) for some \(C\), i.e., \(S = \texttt{)}C\texttt{(}B\). So in order to try to compensate for the imbalance in distribution, we use \(\texttt{(}f(B)\texttt{)}C’\) instead (where \(A’ = (C’)\)). As it turns out, this works out perfectly.

Here’s the formal construction:

Definition: \(f: \cup_{n = 0}^\infty S_n \to \cup_{n = 0}^\infty S^*_n\) is defined as

1. \(f(\varepsilon) = \varepsilon\), where \(\varepsilon\) is the empty string.
2. \(f(AB) = Af(B)\), if \(A\) is irreducible and balanced.
3. \(f(AB) = (f(B))C’\), if \(A\) is irreducible and not balanced, and as a corollary, \(A =\; )C(\) for some \(C\).

Claim: For any string \(S^* \in S^*_n\), there are exactly \(n + 1\) solutions to \(f(S) = S^*\) for \(S \in S_n\).

Proof: Let \(S^* = A^*B^*\), where \(A^*\) is the irreducible prefix of \(S^*\). Let \(S \in S_n\) be a string satisfying the equation \(f(S) = S^*\). We prove this by induction. For \(n = 0\), there is nothing to prove. Let’s suppose \(n > 0\). Then \(S\) can be mapped to \(S^*\) by using one of the two rules, depending on whether the irreducible prefix of \(S\) is a balanced bracket sequence or not:

1. Let \(S = AB\), where \(A\) is a balanced irreducible prefix of \(S\). Then we must have \(S^* = f(S) = A f(B)\). Since \(A, A^*\) are both balanced irreducible prefixes of \(S^*\), they must be equal, and \(B^* = f(B)\). The number of solutions in this case is hence equal to \(\frac{|B^*|}{2} + 1\) by the induction hypothesis.
2. Let \(S = AB\), where \(A\) is not balanced, but an irreducible prefix of \(S\). Then \(A =\; \texttt{)}C\texttt{(}\), and \(A’ = \texttt{(}C’\texttt{)}\) (as mentioned above). By definition, \(S^* = f(S) = \texttt{(}f(B)\texttt{)} C’\). By an analogous argument as above, since \(f(B)\) is balanced, \(A^* = \texttt{(}f(B)\texttt{)}\) and \(B^* = C’\). There are exactly \(\frac{|A|^*}{2}\) solutions as earlier.

Overall, there are \(\frac{|A^*| + |B^*|}{2} + 1 = n + 1\) solutions to \(f(S) = S^*\), as needed.

In fact, if, in the proof, we also keep track of the badness of the strings that generate a given balanced bracket sequence, we can see that there is one input string for each possible value of badness (and this gives an alternative proof of the Chung-Feller theorem).

Generating Balanced Bracket Sequences

It has been asked before on CodeForces \([6]\) how to generate a random bracket sequence. Judging from the comments, no one has been able to figure out how to generate it quickly (i.e. in linear time). So I will provide the code to generate a uniform balanced bracket sequence. Additionally, I will provide code that generates a random binary tree of \(n\) vertices to balanced bracket sequences of size \(2n\).

I know that there is also a bijection between bracket sequences and ordered trees, but there are better ways to generate a tree \([7]\). Also, there is also a bijection to full binary tree of \(2n+1\) vertices, but there is a easy bijection to binary trees of \(n\) vertices noting that the full binary tree of \(2n+1\) vertices has \(n+1\) leaf nodes. We simply remove all leaves, which leaves (pun not intended) us with a binary tree of \(n\) vertices. So the binary tree is the “internal nodes” of the full binary tree.

Also, there is a (rather inelegant) method of generating balanced bracket sequences without using any of the techniques discussed earlier.

One of the first ideas that anyone attempting this task might have is to randomly place \(\texttt{(}\) or \(\texttt{)}\) in a string unless it is impossible to do so. However, we do not get a uniform distribution. Instead, let us vary the probability that we place \((\) or \()\) in accordance to the actual probability that we will see in our required distribution.

Let \(C_n^k\) denote the number of bracket sequences of size \(2n\) with the first \(k\) elements being \(\texttt{(}\). From \([8]\), we know that \(C_n^k = \frac{k+1}{n+1} \binom{2n-k}{n-k} = \frac{k+1}{2n-k+1} \binom{2n-k+1}{n-k}\). We can actually prove it using the same technique of adding a single \(\texttt{)}\) and performing rotations.

Ok, so if we want to make a balanced bracket sequence of length \(2n\) and we currently placed \(a\) \(\texttt{(}\)s and \(b\) \(\texttt{)}\)s, then there are \(C_{n-b}^{a-b}\) possible balanced bracket sequence that have our current string as a prefix. Out of them, \(C_{n-b}^{a+1-b}\) have the next character being \(\texttt{(}\). So we simply calculate the probability that we should put \(\texttt{(}\) as \(\frac{C_{n-b}^{a+1-b}}{C_{n-b}^{a-b}} = \frac{n-a}{2n-a-b} \cdot \frac{a-b+2}{a-b+1}\). Notice that \(n-a\) and \(n-b\) are the remaining numbers of \(\texttt{(}\) s and \(\texttt{)}\) s respectively. The \(\frac{n-a}{2n-a-b}\) term nicely corresponds to the ratio of \(\texttt{(}\) s in the remaining characters.

As for the bijection from balanced bracket sequences to binary trees, remember earlier when we showed the recurrence \(C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}\) by bijecting into pairs \((X,Y)\) such that string is of the form \(\texttt{(}X\texttt{)}Y\). This bijection works for a recursive bijection into binary trees too \([\text{folklore}]\). That is, \(\texttt{()}\) bijects to the binary tree with \(1\) nodes, then for any other bracket sequence, \(X\) describes the left child and \(Y\) describes the right child.

Ok enough talking, here are the codes (I used testlib \([7]\)). They are written by both nor sir and I.

#include <bits/stdc++.h>

#include "testlib.h"

std::string balanced_bracket_sequence_v1(int n) {
    auto res = std::string(n, '(') + std::string(n + 1, ')');
    shuffle(res.begin(), res.end());
    std::vector<int> pref(2 * n + 2, 0);
    for (int x = 0; x < 2 * n + 1; x++)
        pref[x + 1] = pref[x] + (res[x] == '(' ? 1 : -1);
    int idx =
        int(std::min_element(pref.begin(), pref.end()) - pref.begin());
    std::rotate(res.begin(), res.begin() + idx, res.end());
    return res.substr(0, 2 * n);
}

std::string balanced_bracket_sequence_v2(int n) {
    auto a = std::string(n, '(') + std::string(n, ')');
    shuffle(a.begin(), a.end());
    auto output = a;
    for (int l_in = 0, l_out = 0, r_in = 2 * n; l_in < r_in;) {
        int pos = l_in;
        int balance = 0;
        for (; pos != r_in; ++pos)
            if ((balance += (a[pos] == '(' ? +1 : -1)) == 0) break;
        if (a[l_in] == '(') {
            for (; l_in <= pos; ++l_in, ++l_out) output[l_out] = a[l_in];
        } else {
            const int sz_u = r_in - pos - 1, r_out = l_out + sz_u + 1;
            output[l_out] = '(', output[r_out] = ')';
            for (int i = l_in + 1, j = r_out + 1; i != pos; ++i, ++j)
                output[j] = (a[i] == '(' ? ')' : '(');
            l_in = pos + 1;
            l_out++;
        }
    }
    return output;
}

std::string balanced_bracket_sequence_v3(int n) {
    long long a = 0, b = 0;
    std::string res;
    for (int x = 0; x < 2 * n; x++) {
        if (rnd.next((2 * n - a - b) * (a - b + 1)) <
            (n - a) * (a - b + 2)) {
            res += '(';
            a++;
        } else {
            res += ')';
            b++;
        }
    }
    return res;
}

struct tree {
    int node;
    tree *l, *r;
    tree(int node_, tree* l_, tree* r_) : node{node_}, l{l_}, r{r_} {}
};

int get_value(tree* t) {
    if (t) return t->node;
    return -1;
}

using representation_t = std::vector<std::tuple<int, int, char>>;

auto representation(tree* t) {
    representation_t repr;
    auto dfs = [&repr](auto self, tree* a) -> void {
        if (!a) return;
        repr.emplace_back(a->node, get_value(a->l), 'L');
        repr.emplace_back(a->node, get_value(a->r), 'R');
        self(self, a->l);
        self(self, a->r);
    };
    dfs(dfs, t);
    return repr;
}

auto shuffled_representation(int n, representation_t r) {
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end());  // shuffle vertex labels
    for (auto& [n1, n2, dir] : r) {
        if (n1 != -1) n1 = p[n1];
        if (n2 != -1) n2 = p[n2];
    }
    shuffle(r.begin(), r.end());  // shuffle edge order
    return r;
}

tree* binary_tree_from_balanced_bracket_sequence(const std::string& s) {
    int n = int(s.size()) / 2;
    std::vector<int> nxt(2 * n, -1);
    std::vector<int> stk;
    for (int x = 0; x < 2 * n; x++) {
        if (s[x] == '(') {
            stk.push_back(x);
        } else {
            nxt[stk.back()] = x;
            stk.pop_back();
        }
    }
    int node = 0;
    std::vector<tree*> roots(2 * n, nullptr);
    for (int x = 2 * n - 1; x >= 0; x--) {
        if (s[x] == '(') {
            tree *left = nullptr, *right = nullptr;
            if (s[x + 1] == '(') left = roots[x + 1];        // left child
            if (nxt[x] + 1 < 2 * n && s[nxt[x] + 1] == '(')  // right child
                right = roots[nxt[x] + 1];
            roots[x] = new tree(node++, left, right);
        }
    }
    return roots[0];
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n = opt<int>("n");
    int t = opt<int>("t");
    std::cout << t << '\n';
    for (int test = 1; test <= t; ++test) {
        std::cout << n << '\n';
        auto rep = shuffled_representation(
            n, representation(binary_tree_from_balanced_bracket_sequence(
                   balanced_bracket_sequence_v1(n))));
        for (auto [parent, child, direction] : rep)
            std::cout << parent + 1 << ' ' << child + 1 << ' ' << direction
                      << '\n';
    }
}

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

string bSeq(int n,int k) {
    string res=string(n-k,'(')+string(n+1,')');
    shuffle(res.begin(),res.end());
    deque<int> dq(k+1);

    int mn=0;
    int curr=0;
    for (int x=0;x<=2*n-k;x++){
        curr+=(res[x]=='('?1:-1);
        if (curr<mn){
            mn=curr;
            dq.push_back(x);
            dq.pop_front();
        }
    }

    rotate(res.begin(),res.begin()+dq[rnd.next(k+1)]+1,res.end());
    return string(k,'(')+res.substr(0,2*n-k);
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n=atoi(argv[1]),k=atoi(argv[2]);

    cout<<bSeq(n,k)<<endl;
}

A Surprisingly Fast Generation

Thanks to pajenegod for pointing out that this method might be faster than \(O(n^2)\).

Let us return to the original reccurence of \(\texttt{(}X\texttt{)}Y\). This gives us a natural DnC-esque recurence if we are able to determine how to uniformly choose the correct size for \(X\) and \(Y\). Recall that \(C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}\) and that we have the approximation \(C_n \approx \frac{4^n}{\sqrt{\pi n^3}}\) \([1]\).

For some bracket sequence of size \(2(n+1)\), the probability we recurse into \(X\) of size \(s\) is \(P_s = \frac{C_{s}C_{n-s}}{C_{n+1}}\). Of course, we are not able to store \(C_n\) directly, but using the earlier approximation earlier, it makes sense to store \(C’_n = \frac{C_n}{4^n}\), which should be at a reasonable size to use doubles. We can calculate \(C’_{n+1} = \frac{n+\frac{1}{2}}{n+2} \cdot C’_n\) in linear time. Nicely, \(P_s = \frac{C’_{s}C’_{n-s}}{4 C’_{n+1}}\).

Here, we can already bound these types of reccurences by \(O(n \log n)\) if we don’t care about the distribution of \(s\) that we recurse to. We can do this by mapping \(P_s\) in the order of \(P_0,P_n,P_1,P_{n-1},\ldots\). That is, we generate a random number in \(Z=[0,1)\). If \(Z < P_0\), we recurse with \(s=0\), if \(Z < P_0+P_n\), we recurse with \(s=n\), etc.

With this method, our time complexity is actually \(T(n)=O(\min(a,b))+T(a)+T(b)\). So, we have \(T(n)=O(n \log n)\).

But maybe we can do better. Note that the true complexity is \(T(n+1) = \sum\limits_{s=0}^{n} P_s \cdot (T(s) + T(n-s) + O(\min(s,n-s))\)

Let’s look at the distribution of \(P_s\) for \(n=8\).

We see that the distribution is symmetric (which isn’t that important) and that larger values appear on the extreme ends (which is important). This suggests in most cases, our recursion will make one side much smaller than the other.

Let us try to find an approximation for expected value of \(\min(s,n-s)\) when drawn over the probability distribution of \(P_s\). Note that \(P_s = \frac{C’_{s}C’_{n-s}}{4 C’_{n+1}} \approx \frac{\sqrt{n^3}}{4 \sqrt{\pi s^3(n-s)^3}}\).

When \(s \leq \frac{1}{2} n\), we get \(P_s \lessapprox \frac{\sqrt{8}}{4 \sqrt{\pi s^3}} = \frac{1}{\sqrt{2 \pi}} \cdot \frac{1}{\sqrt{s^3}}\).

\[\begin{align}E(\min(a,b)) &= 0 \cdot P_0 + 0 \cdot P_n + 1 \cdot P_1 + 1 \cdot P_{n-1} + \ldots \&= 2 \cdot (\sum_{s=0}^{\frac{n}{2}} s \cdot P_s)\\ &\lessapprox \sqrt{\frac{2}{\pi}} \cdot (\sum_{s=0}^{\frac{n}{2}} \frac{s}{\sqrt{s^3}}) \\ &< \sqrt{\frac{2}{\pi}} \cdot (\int_{0}^{\frac{n}{2}} \frac{1}{\sqrt{s}} \, ds) \\ &= \sqrt{\frac{2}{\pi}} \cdot \sqrt{2n} \\ &= 2 \sqrt{\frac{n}{\pi}} \end{align}\]

So, I thought the reccurence was going to look like \(T(n)=O(\sqrt n) + T(\sqrt n) + T (n - \sqrt n)\). Which gives us \(T(n) = O(n \log \log n)\). But unfortunately, this turned out to not be true.

After empirical testing and explicitly calculating the theoretical value of \(T(n)\), I have observed that the actual complexity is \(O(n \log n)\). I think it is quite interesting that despite our recurrence usually cutting at values of around \(\sqrt n\), we end up having a total complexity of \(O(n \log n)\) anyways, but probably with a significantly large logarithm base.

I’m using a Ryzen 7 3700X CPU with the compile command g++ xxx.cpp -O2.

#include <bits/stdc++.h>
using namespace std;

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);

double cat[10000005];
double t[10000005];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);

    cat[0]=1;
    rep(x,0,10000000) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];

    rep(x,1,100000){
        double tot=0;
        rep(y,0,x){
            double prob=cat[y]*cat[x-y-1]/(4*cat[x]);
            t[x]+=prob*(t[y]+t[x-y-1]+min(y,x-y-1));
            tot+=prob*min(y,x-y-1);
        }
    }

    rep(x,1,100000) cout<<x<<" "<<t[x]<<endl;
}

#include <bits/stdc++.h>
using namespace std;

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);

long long time(){
    return chrono::system_clock::now().time_since_epoch().count();
}

double cat[10000005];

void solve(int pl,int pr,string &s){
    if (pl==pr) return;

    double temp=dist(rng);
    int n=(pr-pl)/2;

    double curr=0;
    int l=0,r=n-1;
    int ss;

    while (true){
        { //add l
            curr+=cat[l]*cat[n-1-l]/(4*cat[n]);
            if (temp<curr){ ss=l; break; }
            l++;
        }
        { //add r
            curr+=cat[r]*cat[n-1-r]/(4*cat[n]);
            if (temp<curr){ ss=r; break; }
            r--;
        }
    }

    s[pl+1+2*ss]=')';
    solve(pl+1,pl+1+2*ss,s);
    solve(pl+2+2*ss,pr,s);
}

string gen(int n){
    cat[0]=1;
    rep(x,0,n) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];

    string res(2*n,'(');
    solve(0,2*n,res);
    return res;
}

signed main(int argc, char *argv[]){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);

    rep(x,0,24){
        long long start=time();
        long long num=0;
        while (time()-start<10000000000){
            gen(1<<x);
            num++;
        }

        long long end=time();
        cout<<(1<<x)<<" "<<num<<" "<<end-start<<" "<<(double)(end-start)/(num*(1<<x))<<endl;
    }
}

1 266547240 10000000078 37.5168
2 187154707 10000000050 26.7159
4 102058691 10000000091 24.4957
8 47076531 10000000131 26.5525
16 22151581 10000000151 28.2147
32 10758623 10000000660 29.0465
64 5403745 10000009142 28.9152
128 2734025 10000000066 28.5751
256 1338297 10000004834 29.1882
512 660750 10000010888 29.5592
1024 328150 10000004632 29.7597
2048 158510 10000011967 30.8045
4096 77867 10000111333 31.3539
8192 38048 10000260495 32.0841
16384 18565 10000365194 32.8777
32768 9273 10000355466 32.9113
65536 4657 10000484304 32.7669
131072 2277 10004361811 33.521
262144 1104 10004416345 34.5687
524288 548 10006717357 34.829
1048576 270 10012533429 35.3655
2097152 130 10035361701 36.8095
4194304 65 10088588940 37.0047
8388608 33 10127937055 36.5862

References

[1] https://en.wikipedia.org/wiki/Catalan_number
[2] https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf
[3] https://www.sciencedirect.com/science/article/pii/S0195669813800534
[4] https://uoj.ac/problem/273
[5] http://www.cs.otago.ac.nz/staffpriv/mike/Papers/RandomGeneration/RandomBinaryTrees.pdf
[6] https://codeforces.com/blog/entry/45723
[7] https://codeforces.com/blog/entry/18291
[8] https://codeforces.com/blog/entry/87585