1
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 4, 2016 at 20:07
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2016 at 21:32
  • $\begingroup$ @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. $\endgroup$
    – Cain
    Apr 4, 2016 at 23:02

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks Robert. Much appreciated and confirms what I suspected. I have added a second question from my book which I am hoping will actually be a proper example. $\endgroup$
    – Cain
    Apr 4, 2016 at 20:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .