# Bijection and catalan numbers

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.

• Are you sure that you quoted the problem correctly? As I read it, the number of such permutations is $\binom{2n}nn!$, which is not a Catalan number. Apr 4, 2016 at 20:07
• I think you might be reading the problem wrong. That's not a second example, I think it's supposed to be BOTH of those things. And there's probably a third like "For any even number $2k$, there are at least $k$ odd numbers appearing before it". At that point, there's a pretty obvious bijection to Dyck paths. Apr 4, 2016 at 21:32
• @callus you are definitely right! I found it ambiguous as they were numbers and not bullet points in the book and thought it has to prove it for them separately. Now that I look at it it is definitely obvious.
– Cain
Apr 4, 2016 at 23:02

For the record, for the updated question with three simultaneous conditions, there is an obvious correspondence with Dyck words. The first two conditions ensure that a configuration satisfying them is entirely determined by specifying for each position whether it contains an odd or an even number. This can be represented by a word of length $$2n$$ over a two-letter alphabet, say $$\{A,B\}$$ with $$A$$ marking the odd-value positions and $$B$$ the even-value position. The final condition then says that for every $$k$$, the $$k$$-th occurrence of $$A$$ precedes the $$k$$-th occurrence of $$B$$, and this is precisely the condition that defines Dyck words.
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.