I am having trouble with bijection and Catalan numbers. Here is a sample of a problem I am working with.
Give a bijection to show that the following is counted by Catalan numbers. The number of orderings of numbers in $\{1,2,...,2n\}$ such that
- the odd numbers $1,3,...,2n-1$ appear in order among each other,
- the even numbers $2,4,...,2n$ appear in order among each other,
- the number $2k-1$ precedes $2k$ for every $1\leq k\leq n$.
I'm at a loss but feel Dyck walks may be involved.
Can anybody point me in the right direction?
Edit: It appears the first example I listed from my book is not a Catalan number. I have added a second one.
Final edit: I had read the question wrong. I needed to prove the bijection for a set that had all the following characteristics at once and not prove the bijection for all three sets separately.
A Dyck walk is indeed the right approach.
To get such an ordering of $\{1,\ldots, 2n\}$, you might first choose which $n$ of $1,\ldots, 2n$ correspond to the odd numbers, put those odd numbers $1,3,\ldots, 2n-1$ in those positions in order, and then put the even numbers $2,4,\ldots,2n$ into the remaining $n$ positions in any way. The number of ways to do this is $$ {2n \choose n} n! = \dfrac{(2n)!}{n!}$$ That is not a Catalan number.
EDIT: For the revised question (where you want both the even and the odd numbers in order), the number of possibilities is just ${2n \choose n}$. That's still not Catalan.