
doi: 10.37236/430
A matching of size $2n$ is a partition of the set $[2n]=\{1,2,\dotsc,2n\}$ into $n$ disjoint pairs. A matching may be identified with a canonical sequence, which is a sequence of integers in which each integer $i\in[n]$ occurs exactly twice, and the first occurrence of $i$ precedes the first occurrence of $i+1$. A partial pattern with $k$ symbols is a sequence of integers from the set $[k]$, in which each $i\in[k]$ appears at least once and at most twice, and the first occurrence of $i$ always precedes the first occurrence of $i+1$. Given a partial pattern $\sigma$ and a matching $\mu$, we say that $\mu$ avoids $\sigma$ if the canonical sequence of $\mu$ has no subsequence order-isomorphic to $\sigma$. Two partial patterns $\tau$ and $\sigma$ are equivalent if there is a size-preserving bijection between $\tau$-avoiding and $\sigma$-avoiding matchings. In this paper, we describe several families of equivalent pairs of patterns, most of them involving infinitely many equivalent pairs. We verify by computer enumeration that these families contain all the equivalences among patterns of length at most six. Many of our arguments exploit a close connection between partial patterns and fillings of diagrams.
Permutations, words, matrices, Partitions of sets, matching, avoiding, partial pattern, Exact enumeration problems, generating functions, canonical sequence
Permutations, words, matrices, Partitions of sets, matching, avoiding, partial pattern, Exact enumeration problems, generating functions, canonical sequence
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
