Using parallel specifications to discover bijections
Most of the time we use TileScope to find a specification for a single permutation class, and if we find one we can use it to count the class. Here we show how TileScope can be used to find specifications for two classes simultaneously, that are similar enough (parallel), so that we can prove a bijection between the classes.
Finding two specifications of the same shape
TileScope expands the two classes' universes, each on its own, until each holds a specification. Then the parallel search pairs a class of one universe with a class of the other, from the two roots down: two rules with the same kind of counting constructor, each part of one paired with a part of the other, until every pair ends in two single points or recurses.
The two specifications, and the bijection they give
Each rule of one is matched to a rule of the other, of the same kind and with as many parts, and the pairs are numbered alike on both sides. A tiling can be in more than one pair. A step that only makes a tiling into an equivalent one, such as separating its rows and columns, is passed over, and its tiling has the numbers of the pair it leads to, hollow.
The bijection: \(w\) is taken apart down the first specification until every entry is a single point. Each point goes to the leaf of the second specification paired with its own, and the second specification builds the points up, rule by matched rule, into \(\varphi(w)\). Each point keeps its color, from \(w\) to \(\varphi(w)\).
Where each point goes
The plot of \(w\) turns into the plot of \(\varphi(w)\) twice, each point moving across to its new column and then up or down to its value there. On the left, every point moves to the point it becomes, the one paired with it through the two specifications. On the right, only the points that must move do so. On the left, a point often moves into a place that another point of \(w\) held, and that point moves on in turn. On the right, the points along such a chain stay where they are, and the chain's first point goes straight to its end, so every point in a column where \(w\) and \(\varphi(w)\) agree stays put.
Claesson and Kitaev's ten bijections
Anders Claesson and Sergey Kitaev, in Classification of bijections between 321- and 132-avoiding permutations (Séminaire Lotharingien de Combinatoire 60, 2008, Article B60d), gather ten bijections, each called by the names of those who found it, and sort them into five classes. Each bijection goes between (a symmetry of) \(\operatorname{Av}(123)\) and (a symmetry of) \(\operatorname{Av}(132)\). Two bijections are in the same class when one is related to the other through symmetries.
Each of the ten is implemented here from the paper's definition and checked against its examples and its classes. We ran the parallel search on every pair of symmetries of the two classes, with several packs, and compared each bijection found with the ten.