equivalence classes of arch diagrams in bijection with permutations

Question

By an arch diagram of size $n$, I mean a diagram consisting of $n$ arches matching $2n$ points, where the points are ordered on a line running from left to right. An arch diagram is basically just a way of representing a fixed-point free involution in $S_{2n}$, and arch diagrams of size $n$ are counted by the double factorial numbers (A001147) $$1, 1, 3, 15, 105, 945, 10395, ...$$ A special class of arch diagrams are the non-crossing (planar) arch diagrams, which are in bijection with (rooted planar) binary trees and are counted by the Catalan numbers (A000108) $$1, 1, 2, 5, 14, 42, 132, ...$$ My question is about a family of arch diagrams living between these two extremes, or really about a family of equivalence classes of arch diagrams.

Let's say that two arcs of an arch diagram are left-adjacent if their left end points are adjacent in the linear order. Then say that two arch diagrams are equivalent modulo left-adjacency if one can be obtained from the other by successively swapping left endpoints of left-adjacent arches. For example, among the three arch diagrams of size 2, diagrams (2) and (3) are equivalent modulo left-adjacency, but neither is equivalent to (1).

One (somewhat arbitrary) way of picking a canonical representative of each equivalence class is to enforce the condition that $$ i < \alpha_i \text{ and } i' < \alpha_{i'} \text{ implies } \alpha_i > \alpha_{i'} $$ for all $1 \le i\le 2n-1$ and $i' = i+1$, where $\alpha \in S_{2n}$ is the fixed-point free involution corresponding to the arch diagram. For example, this way of choosing representatives yields the following arch diagrams of sizes $1..4$: In any case, it appears that equivalence classes of arch diagrams modulo left-adjacency are counted by the factorial numbers (A000142) $$1, 1, 2, 6, 24, 120, 720, ...$$ I've managed to convince myself of this by considering a more general notion of arch diagram allowing unattached points (corresponding to fixed points of the associated involution), and defining a two-variable generating function $A(x,z)$ counting equivalence classes of arch diagrams by number of unattached points ($x$) and arches ($z$). An inductive decomposition of this family of equivalence classes of (generalized) arch diagrams implies that $$A(x,z) = 1 + \sum_k \frac{z^k}{k!} \cdot \frac{\partial^k x\cdot A(x,z)}{\partial x^k} = 1 + (x+z)\cdot A(x+z,z)$$ from which $A(0,z) = \sum_n n! \cdot z^n$ follows.

My questions are:

1. Has this equivalence relation on arch diagrams been previously studied, and is there a standard name for arch diagrams modulo this equivalence relation?
2. Is there a simple bijective proof of the fact that equivalence classes of arch diagrams modulo left-adjacency are counted by the factorial numbers?

Answer 1

Let me address Q2.

Paint all right endpoints in white, and all left ones in black. Number white points $1,2,\dots,n$ from left to right, and number the black points according to the numbers of white points joined to them.

All black points lying between two consecutive white ones can be permuted arbitrarily. So the only thing that matters for a black point is in which of the $n$ intervals (before 1, and between $i$ and $i+1$ for some $i$) it is situated. For the $i$th black point, there are $i$ possible options. Altogether, we get $1\cdot 2\cdots n=n!$ variants.

Answer 2

Looking at your examples, these diagrams are familiar.

Number the points from 1 to $2n$. Then every arc connects an even point and an odd point. This is a bijection between the even points and the odd points. The number of bijections is $n!$.

It remains to show that these are your diagrams.