Balanced bracket words, defined by the recursive grammar

Let $\mathrm{\Sigma }:=\{\mathtt{\text{(}},\mathtt{\text{)}}\}$ and let ${\mathrm{\Sigma }}^{\ast }:={\bigcup }_{\mathrm{\ell }\in \mathbb{N}}{\mathrm{\Sigma }}^{\mathrm{\ell }}$ be the set of all finite words over $\mathrm{\Sigma }$, the words of length $\mathrm{\ell }$ being the functions $\{0,\dots ,\mathrm{\ell }-1\}\to \mathrm{\Sigma }$ (Finite words, contiguous factors, avoidance and proper-prefix states). Write $\epsilon$ for the empty word and $uv$ for concatenation.

Call a set $X\subseteq {\mathrm{\Sigma }}^{\ast }$ grammatical when $\epsilon \in X$ and $\mathtt{\text{(}}u\mathtt{\text{)}}v\in X$ for all $u,v\in X$. The set ${\mathrm{\Sigma }}^{\ast }$ itself is grammatical, so the family of grammatical subsets is a nonempty subfamily of $\mathcal{P}({\mathrm{\Sigma }}^{\ast })$ (The power set $\mathcal{P}(x)=\{z:z\subseteq x\}$), and we may define

$\mathcal{B}:=\bigcap \{X\subseteq {\mathrm{\Sigma }}^{\ast }:X\text{ is grammatical}\},$

the balanced bracket words. Thus $\mathcal{B}$ is itself grammatical, and it is contained in every grammatical set.

Structural induction, which is what the definition is for. If $X\subseteq \mathcal{B}$ is grammatical then $X=\mathcal{B}$, since $\mathcal{B}$ is contained in every grammatical set. So to prove that every balanced bracket word has a property it suffices to prove it for $\epsilon$ and to prove it for $\mathtt{\text{(}}u\mathtt{\text{)}}v$ whenever it holds for $u$ and for $v$.

Every nonempty balanced word factors as $\mathtt{\text{(}}u\mathtt{\text{)}}v$. Put ${\mathcal{B}}^{\mathrm{\prime }}:=\{\epsilon \}\cup \{\mathtt{\text{(}}u\mathtt{\text{)}}v:u,v\in \mathcal{B}\}$. Then ${\mathcal{B}}^{\mathrm{\prime }}\subseteq \mathcal{B}$ because $\mathcal{B}$ is grammatical, and ${\mathcal{B}}^{\mathrm{\prime }}$ is itself grammatical: it contains $\epsilon$, and if $u,v\in {\mathcal{B}}^{\mathrm{\prime }}$ then $u,v\in \mathcal{B}$, so $\mathtt{\text{(}}u\mathtt{\text{)}}v\in {\mathcal{B}}^{\mathrm{\prime }}$ by construction. By the previous paragraph ${\mathcal{B}}^{\mathrm{\prime }}=\mathcal{B}$, which is the assertion.

Lengths. Every $w\in \mathcal{B}$ has even length: this holds for $\epsilon$, and if $u$ and $v$ have even lengths then so does $\mathtt{\text{(}}u\mathtt{\text{)}}v$, whose length is $\mid u\mid +\mid v\mid +2$. So put, for $n\in \mathbb{N}$,

${\mathcal{B}}_n:=\{w\in \mathcal{B}:\mid w\mid =2n\}\mathrm{.}$

Then ${\mathcal{B}}_0=\{\epsilon \}$, since a balanced word of length $0$ is $\epsilon$ and $\epsilon \in \mathcal{B}$; and for every $n$,

${\mathcal{B}}_{n+1}={\bigcup }_{i\le n}\{\mathtt{\text{(}}u\mathtt{\text{)}}v:u\in {\mathcal{B}}_i,v\in {\mathcal{B}}_{n-i}\},$

by the factorisation clause together with the additivity of lengths. In particular ${\mathcal{B}}_1=\{\mathtt{\text{()}}\}$ and ${\mathcal{B}}_2=\{\mathtt{\text{(())}},\mathtt{\text{()()}}\}$.

Each ${\mathcal{B}}_n$ is finite, being a subset of the set ${\mathrm{\Sigma }}^{2n}$ of words of length $2n$, which is finite with $2^{2n}$ elements (The set $A^B$ of functions $B\to A$ between finite sets is finite, with $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$, A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, The cardinality $\mid A\mid$ of a finite set).

• The grammar is the definition, and that is deliberate. The set could instead have been defined by the counting condition — every prefix has at least as many $\mathtt{\text{(}}$ as $\mathtt{\text{)}}$, with equal totals — and then the theorem that follows would be a tautology. Taking the recursive description as the definition makes the equivalence of the two descriptions something to prove, and it is that equivalence that the counting arguments use.

• No parser and no stack. The definition quantifies over subsets of ${\mathrm{\Sigma }}^{\ast }$ and takes an intersection. Nothing about reading a word left to right is assumed; the left-to-right characterisation is the content of the next item.

• Why the graded pieces are indexed by half the length. A balanced word has even length, and every count on this page is stated in the number of bracket pairs. The displayed recursion for ${\mathcal{B}}_{n+1}$ is the same shape as the first-return decomposition of a Dyck path, which is why the two families have the same counts.