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$?

  • $\begingroup$ Are you preserving the orders of the sequences as in the original question? Which conditions are you trying to insist upon and which properties are given? $\endgroup$ Jun 21 '18 at 14:52
  • $\begingroup$ Thanks for the questions. I've added a paragraph to try to clarify. $\endgroup$
    – Fantastic
    Jun 21 '18 at 15:43

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.