$n$- transposition permutations in $S_{2n}$ which decompose a $2n$-cycle into $n+1$ cycles

Question

I was learning about Catalan numbers online. I have understood the combinatorial argument, recurrence relation and generating function based proofs of Dyck words and Dyck paths.

Let $S_{2n}$ be the symmetric group of permutations on integers $1$ through $2n$.

Consider the conjugacy class of the permutation $(1, 2)(3, 4)(5, 6)\ldots(2n-1, 2n)$ in $S_{2n}$. Let's denote it by $W_{2n}$. [N.B. Conjugacy preserves cycle structure, so what I mean is that $W_{2n}\ \left(\subset S_{2n}\right)$ is the set of all permutations which can be expressed as product of $n$ mutually disjoint transpositions.]

Check that: $$|W_{2n}|=\frac{1}{n!}\binom{2n}{2}\binom{2n-2}{2}\binom{2n-4}{2}\cdots \binom{2}{2}=\frac{(2n)!}{2^n\cdot n!}$$

Since disjoint transpositions commute, every ordering should be counted once. That accounts for the division by $n!$.

In bijective proof problems (problem 175, page 41), I came across the fact that the number of permutations $w\in W_{2n}$ such that the product $(1,2,\ldots,2n) \circ w$ has $(n+1)$ disjoint cycles is given by the $n$-th Catalan number.

How do I prove this?

For example, in the group $S_6$, there are $5$ permutations $w\in W_{6}$ (consisting of $3$ disjoint transpositions each) such that the product $(1,2,3,4,5,6)\circ w$ has $4$ disjoint cycles.

1. $(1, 2, 3, 4, 5, 6)\circ(1, 2)(3, 4)(5, 6) = (1, 3, 5)(2)(4)(6)$
2. $(1, 2, 3, 4, 5, 6)\circ(1, 2)(3, 6)(4, 5) = (1, 3)(2)(4, 6)(5)$
3. $(1, 2, 3, 4, 5, 6)\circ (1, 4)(2, 3)(5, 6) = (1, 5)(2, 4)(3)(6)$
4. $(1, 2, 3, 4, 5, 6)\circ (1, 6)(2, 3)(4, 5) = (1)(2, 4, 6)(3)(5)$
5. $(1, 2, 3, 4, 5, 6)\circ (1, 6)(2, 5)(3, 4) = (1)(2, 6)(3, 5)(4)$

I have been trying to construct a bijective mapping of these permutations with Dyck words of length $2n$ but unable to make it. How do I progress with this approach? Is there a better alternate approach i.e., a clever combinatorial argument?

I am a beginner in abstract algebra, I understand order, compositions, etc. of the elements of symmetric group; I don't have much in depth knowledge on this topic. It is possible that I might be missing out on some obvious property of the permutations/cycles which can potentially help solve this problem.

Answer 1

Observe that the $5$ valid permutations share a property in common:

• When we regard transposition $(x \; y)$ (w.l.o.g. $x < y$) as a left bracket "(" at $x$-th position and a right bracket ")" at $y$-th position, the bracket sequence is valid, and positions of each transposition form pairs of matched brackets.

This hints us to regard each transposition as matched pairs and to consider similar combinatorial objects.

And you are right, one property of permutations/cycles/transposition really helps (me).

You should be familiar with this characterization of Catalan number:

• $C_n$ is the number of ways to draw $n$ non-intersecting chords joining $2 n$ labelled points on a circle. (Problem 161 in Stanley’s bij book)

And we can make a bijection between your problem and this characterization, as follows...

1. The problem is to count, a $(2 n)$-cycle, right-multiplied by $n$ transpositions one by one, and at the end, decomposed into $(n + 1)$ disjoint cycles. What makes that possible?
2. We claim that: For a permutation $\sigma \in S_{2 n}$, which has $k$ cycles, when it is right-multiplied by a transposition $(x \; y)$, the resulting permutation contains either $(k + 1)$ or $(k - 1)$ cycles. Specifically, if $x, y$ belong to the same cycle in the original $\sigma$, there’re $(k + 1)$ cycles; otherwise ($x, y$ belong to different cycles) there’re $(k - 1)$ cycles. (Prove this by yourself!)
3. Initially there’s $1$ cycle, and after $n$ multiplications, there’re $(n + 1)$ cycles. This means, to meet the requirement, each multiplication must meet the condition that results in increasing the number of cycles, that is, each transposition must have $x, y$ belong to the same cycle.
4. When a cycle multiplied by $(x \; y)$, it splits into two cycles by breaking at the positions of $x$ and $y$.
   Example: $(4 \; {\color{red}{7}} \; 1 \; 5 \; {\color{blue}{2}} \; 6 \; 3) \cdot ({\color{blue}{2}} \; {\color{red}{7}}) = (1 \; 5 \; {\color{blue}{2}}) \cdot (4 \; {\color{red}{7}} \; 6 \; 3)$.
   If we consider a cycle as a circle, this acts like cutting the circle into two pieces.
5. Now consider why this is identical to the $n$ non-intersecting chords.
   • If the chords are non-intersecting, are the corresponding transpositions valid?
   • If there are two chords intersect with each other, what happens when the initial cycle multiplied by them in order?

Above are my sketch of this approach. You may fill in the details by yourself.