Interlacing two ordered sequences with constraints How many ways can we create a sequence of length $2n$ from $\\{x_i\\}_{i=1}^n$ and $\\{y_j\\}_{j=1}^n$ so that $x_1<x_2<\cdots <x_n$, $\;y_1<y_2<\cdots <y_n$ and $x_i<y_i$ for all $1\leq i\leq n$ ? This question is related to the following enter link description here, but with an extra condition on the ordering between the two sequences. Using the wordings in the original question: Suppose we have two finite, ordered sequences $x=(x_1,\cdots,x_n)$ and $y=(y_1,\cdots,y_n)$. How many ways can we create a new sequence of length $2n$ from $x$ and $y$ so that the order of elements is preserved AND we have orderings $(x_i,y_i)$ for all $i$?

The Catalan number.

If a's are left parentheses and b's are right parentheses, the condition translates into "there are less then i right parentheses to the left of the i-th left parenthesis".

e.g. For n = 3 we have

$(\ )(\ )(\ ),\ (\ )((\ )),\ ((\ ))(\ ),\ ((\ )(\ )),\ (((\ )))$ or

$a_1b_1a_2b_2a_3b_3,\ a_1b_1a_2a_3b_2b_3,\ a_1a_2b_1b_2a_3b_3, \ a_1a_2b_1a_3b_2b_3,\ a_1a_2a_3b_1b_2b_3$