Is this a valid bijection from this set of permutations to the set of bracket nestings of order $n$?

Question

I'm trying to prove that the set of permutations of $[n]$ which do not contain a decreasing subsequence of order $\geq 3$ is equal to the $n^{th}$ Catalan Number. One of the many things that the Catalan Numbers count is the set of valid parentheses of order $n$, so for example $$()()\text{ and }(())$$ are the valid parentheses (or bracket nestings) of order $2$, equal to the $2^{\text{nd}}$ Catalan Number, $2$. Here is an attempted bijection I've tried:

• Write the permutation down in its normal form, ie. $$1324$$
• If an element is not the first element of any decreasing subsequence, parenthesize it. $$(1)3(2)(4)$$
• Parenthesize the decreasing subsequence (in case an element is part of more than one, then the longest). $$(1)(3(2))(4)$$
• Remove the elements to obtain $$1324\mapsto()(())()$$

I've tried this for the permutations of order $3$, and seems to work:

$$123\mapsto()()()$$ $$132\mapsto()(())$$ $$213\mapsto(())()$$ $$231\mapsto((()))$$ $$312\mapsto(()())$$

If this bijection is valid, then my initial proposition is proven.

Is this a valid bijection?

EDIT: It also works for $n=4$. Could the proof of bijection follow from the uniqueness of the transposition decomposition?

Answer 1

Well, you've defined the forward map from permutations of $n$ with no decreasing sequences of length $>3$, and it's relatively easy to see that always works. So all that's left is to define the reverse mapping and see that that always works in order to prove a bijection.

In any valid string, one of two things must be true:

1. The string can be split into two or more substrings, such that each substring is a valid string. (Ie. there are the same number of opening and closing brackets within each substring.)
2. The string is of the form (substring). (That is, there's a pair of brackets which surround a valid substring.)

Proof: Read along the string and keep a running tally of the function #left brackets - #right brackets. If it's ever zero before the end of the substring, case 1 is true. Otherwise, it must always be $\ge1$ (by definition, it can't be $<0$.) So, it is always wrapped in a set of parentheses which are never escaped from the entire length of the string, and case 2 is true. $\square$

We can use this to solve the problem recursively. In each case:

1. The string splits into 2 substrings, and every element in the left substring must be less than every element in the right substring, otherwise there would be a bracket that wouldn't close, and it wouldn't be a valid substring. (If it split into $n$ substrings, then each substring would contain numbers greater than all the substrings that came before, and less than all the substrings that came after.)
2. There is a pair of brackets surrounding a valid substring - this implies the first element is greater than the last. Further, they must be consecutive, since if the sequence $[a,b,c,...,i]$ had another number $k$ such that $a>k>i$, then that would be a decreasing sequence of length $3$, which is forbidden. From there, you can strip the sequence of its outer brackets, which is equivalent to solving the string without it's first element. Your result will look like $[b,c,...,i]$ - from there, take every element of your list that's $>i$, and add 1 to it, and prepend the string with $i+1$, which solves your original string.

That second case took a lot more thought than I expected to to make sure it worked correctly, and I'm not sure I explained it well. Still, I enjoyed the brain teaser. Thanks for asking this.