Prove that there is a bijection between the set of arrays of size [2 x n] and matched strings of brackets.

Question

Suppose that you've got numbers from $1$ to $2n$ without any duplicates. You can arrange them in an array of size $2 \times n$ so that both rows and columns were in an increasing order. Let say now that you have a set $A_n$ of all such arrays for given $n$.

Example of such an array for n=5: \begin{array}{ccccc} 1 & 2 & 4 & 6 & 9 \\ 3 & 5 & 7 & 8 & 10 \end{array}

There is also a set $B_n$ of matched strings of brackets of length $2n$ (i.e. each string has $n$ pairs of brackets).

Example of such a string for $n=5$: $[\,[\,]\,[\,]\,[\,]\,]\,[\,]$

More formally the matched string of brackets can be constructed according to the following rules:

1. $\lambda \in B_0$, where $\lambda$ is an empty string
2. $x \in B_n, y \in B_m \implies [x]y \in B_{n+m+1}$

Claim: There is a bijection between sets $A_n$ and $B_n$.

For instance given an array from the first example we can build the string from the second example by writing $[$ in the positions from the upper row and $]$ - in the positions from the lower row. It is also not difficult to construct the array from the string.

That is intuitively the claim seems to be correct. However I can't grasp why it must be always correct? Does anybody know how to prove the claim?

Answer 1

Consider a well-formed matrix $\alpha_n$ in $A_n$. Let $x_i$ denote the $i$th element in the top row and let $y_i$ denote the $i$th element in the bottow rom. Then we must have $x_i < y_i$ for all $i \in [0;n]$ and $x_i < y_i$ for all $i \in [0;n]$.

The bijection between $A_n$ and $B_n$ is given by

$$f(\alpha_n) = h(1) h(2) \ldots h(2n)$$

where

$$h(k) = \begin{cases} [ & \text{ if } x_i = k \text{ for some }i \\ ] & \text{ if } y_i = k \text{ for some }i \end{cases} $$

It is easy to see that $f$ is injective, for if $\alpha_n \neq \alpha'_n$, then the two matrices must differ in at least two places, so $f(\alpha_n) \neq f(\alpha'_n)$.

It now remains to be shown that

1. For every $\alpha_n \in A_n$, $f(\alpha_n)$ is an element of $B_n$
2. For every $w \in B_n$ there exists a $\alpha_n \in A_n$ such that $f(\alpha_n) = w$

One proves (1) by induction on $n$.

The base case $n=1$ is simple. The inductive step requires a detailed analysis of the possible contents of a matrix $\alpha_{n+1}$.

One proves (2) by constructing an inverse $g$. This function is defined by

$$g(a_1 \ldots a_{2n}) = \alpha_n$$

where $x_i = k$ if $a_k = [$ and $y_i = k$ if $a_k = ]$. From the definition of $g$ it is straightforward to see that $(g \circ f)(\alpha_n) = \alpha_n$.

Answer 2

I'm pretty sure the bijection is simply the relation that you've suggested. Given the array, we can write the open brackets in the positions in the first row and the closed brackets in the positions from the second row. To show the map is a bijection, we must show it is both onto and into (surjective and injective). It's pretty clearly onto, as any "correct" string of brackets will be represented in the form of an array in $A_n$, with the open brackets always having a matching closed bracket in a greater position. It is also into, as each array maps to a unique string of brackets. So you already have your bijection. I'm being pretty handwavy, but hopefully this gives you an idea of how to proceed.