# equivalence classes of arch diagrams in bijection with permutations

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?
• I unfortunately don't have time to check out all the details but it appears to me that the normalized arch diagrams in your picture above can be interpreted as the cycle diagrams of permutations on $n$ points, by thinking of each adjacent pair of dots, starting from the left, as a single node, and following the arches around the nodes starting with the first one (i.e. the one incident to the first point). This would answer question 2 if the details can be worked out. Sep 8 '16 at 3:05
• I feel like this might be related to hyperplane arrangements, and in particular the following paper: arxiv.org/abs/1604.06554 Sep 8 '16 at 4:18
• @benblumsmith I don't quite understand your suggestion, though I share the intuition that it might be possible to read the normalized arch diagrams as encoding cycle decompositions of permutations. It also appears that the two-variable generating function $A(x,z)$ is the bivariate OGF for unsigned Stirling numbers of the first kind, which seems relevant. Sep 8 '16 at 14:24
• @SamHopkins thanks for the reference. I don't know enough about hyperplane arrangements to see the connection, but I'll let it stew :-) Sep 8 '16 at 14:26
• @NoamZeilberger - I thought about it more and don't think it quite works. The translation I had in mind is not bijective from normalized arch diagrams to permutations. Ilya Bogdanov's answer seems to answer question 2 though. Sep 8 '16 at 19:24

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.

• I'm still interested if anyone has seen this notion of equivalence on arch diagrams (or an isomorphic structure) considered before (i.e., Q1), but since this is a great bijective proof I'm marking the question as answered. Sep 8 '16 at 20:39
• Possibly you can turn this into a bijection using a kind of "histoires" in the spirit of Francon-Viennot. Reading the arch diagram from right to left build a Dyck path with labels on the up-steps as follows: turn a closer into a down-step, and an opener into an up step, labelled with the index of the corresponding closer within the set of closers whose opener has not yet been encountered (1 being the right most possibility). The condition on the labels then might be: between 1 and the height of the current step, and labels of consecutive up steps must be strictly increasing. Unchecked! Sep 9 '16 at 10:23

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.

• There are diagrams where points of the same parity are connected. Sep 8 '16 at 19:56