Skip to main content
use $n$ for index
Source Link

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, 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$: representatives of equivalence classes of arch diagrams of size <span class=$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_k k! \cdot z^k$$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?

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, 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$: representatives of equivalence classes of arch diagrams of size <span class=$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_k k! \cdot z^k$ 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?

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, 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$: representatives of equivalence classes of arch diagrams of size <span class=$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?
Source Link

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, 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$: representatives of equivalence classes of arch diagrams of size <span class=$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_k k! \cdot z^k$ 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?