Definition. For a binary string ss, define

σ(s)= number of 0 in s,λ(s)= number of 1 in s. \begin{aligned} \sigma(s) &= \text{ number of 0 in } s, \\ \lambda(s) &= \text{ number of 1 in } s. \end{aligned}

Definition. Given a binary string ss, denote its length as ∣s∣|s|. For all i∈[∣s∣]i \in [ |s| ], the prefix of length ii, denoted as s[1:i]s[1:i], is the binary string that consists of the first ii bits of ss.

Definition. Let SS be the set of binary strings with nn zeros and nn ones, i.e.,

S≐{s:s∈{0,1}2n∧σ(s)=λ(s)}. S \doteq \{ s : s \in \{ 0, 1 \}^{2n} \wedge \sigma(s) = \lambda(s) \}.

Of interest is the subset P⊂SP \subset S that contains strings whose prefixes have more (or equal) number of 00 than 11:

P≐{s:σ(s[1:i])≥λ(s[1:i]),∀i∈[2n]}. P \doteq \{ s : \sigma(s[1:i]) \ge \lambda(s[1:i]), \forall i \in [2n] \}.

Theorem. The size of PP, denoted as ∣P∣|P|, equals the Catalan number CnC_n defined as

∣Cn∣=1n+1(2nn). |C_n| = \frac{1}{n + 1} \binom{2n}{n}.

Let S∖PS \setminus P be the set of strings that do not satisfy the requirement and define

T≐{s:s∈(0,1)2n∧σ(s)=n−1∧λ(s)=n+1}. T \doteq \{ s : s \in (0, 1)^{2n} \wedge \sigma(s) = n - 1 \wedge \lambda(s) = n + 1 \}.

The proof relies on the following lemma.

Lemma. There is a bijection ff between S∖PS \setminus P and TT.

Before we prove it, we see how it gives Catalan number:

∣P∣=∣S∣−∣S∖P∣=(2nn)−∣T∣=(2nn)−(2nn−1)=(2nn)−(2nn)nn+1=1n+1(2nn) \begin{aligned} |P| &= |S| - |S\setminus P| \\ &= \binom{2n}{n} - |T| \\ &= \binom{2n}{n} - \binom{2n}{n - 1} \\ &= \binom{2n}{n} - \binom{2n}{n} \frac{n}{n + 1} \\ &= \frac{1}{n + 1} \binom{2n}{n} \end{aligned}

Proof of Lemma.

⟶\longrightarrow:

If s∈S∖Ps \in S \setminus P, then there exists some i∈[1,n−1]i \in [1, n - 1], such that σ(s[1:i])<λ(s[1:i])\sigma(s[1:i]) < \lambda(s[1:i]). Then we can select the smallest such ii. Note the ii must be an odd number. Hence we can write i=2j+1i = 2j + 1, σ(s[1:i])=j\sigma(s[1:i]) = j and λ(s[1:i])=j+1\lambda(s[1:i]) = j + 1.

Further, as s∈Ss \in S, we have σ(s)=λ(s)=n\sigma(s) = \lambda(s) = n. Therefore,

σ(s[i+1:n])=n−jλ(s[i+1:n])=n−j−1 \sigma(s[i + 1:n]) = n - j \\ \lambda(s[i + 1:n]) = n - j - 1

To construct an s′∈Ts' \in T from ss, we can flipped every bit in s[i+1:n]s[i + 1:n], i.e.,

s′=(s[1:i],  s[i+1:n]‾) s' = (s[1:i], \ \ \overline{s[i + 1:n] } )

For sanity check, the number of zeros in s′s' is j+n−j−1=n−1j + n -j - 1 = n - 1 and the number of ones is j+1+n−j=n+1j + 1 + n - j = n + 1.

It is easy to see that this is a injection.

⟵\longleftarrow:

If s′∈Ts' \in T, then there must exist some i∈[1,n−1]i \in [1, n - 1], such that σ(s′[1:i])<λ(s′[1:i])\sigma(s'[1:i]) < \lambda(s'[1:i]). Then we can select the smallest such ii. Note the ii must be an odd number. Hence we can write i=2j+1i = 2j + 1, σ(s′[1:i])=j\sigma(s'[1:i]) = j and λ(s′[1:i])=j+1\lambda(s'[1:i]) = j + 1.

Further, as s′∈Ts' \in T, we have σ(s′)=n−1\sigma(s') = n - 1 and λ(s′)=n+1\lambda(s') = n + 1. Therefore,

σ(s′[i+1:n])=n−1−jλ(s′[i+1:n])=n+1−j−1=n−j \sigma(s'[i + 1:n]) = n - 1 - j\\ \lambda(s'[i + 1:n]) = n + 1 - j - 1 = n - j

To construct an s∈S∖Ps \in S \setminus P from s′s', we can flipped every bit in s′[i+1:n]s'[i + 1:n], i.e.,

s=(s′[1:i],  s′[i+1:n]‾) s = (s'[1:i], \ \ \overline{s'[i + 1:n] } )

For sanity check, the number of zeros in ss is j+n−j=nj + n - j = n and the number of ones is j+1+n−1−j=nj + 1 + n - 1 - j = n.

It is easy to see that this is a injection.