In 2000 Klazar introduced a new notion of pattern avoidance in the context of set partitions of \([n]=\{1,\ldots, n\}\). The purpose of the present paper is to undertake a study of the concept of Wilf-equivalence based on Klazar’s notion. We…
Category: original research
Proofs and generalizations of a homomesy conjecture of Propp and Roby
Let \(G\) be a group acting on a set \(X\) of combinatorial objects, with finite orbits, and consider a statistic \(\xi : X \to \mathbb{C}\). Propp and Roby defined the triple \((X, G, \xi)\) to be \emph{homomesic} if for any…
Egge triples and unbalanced Wilf-equivalence
Egge conjectured that permutations avoiding the set of patterns \(\{2143,3142,\tau\}\), where \(\tau\in\{246135,254613,524361,546132,263514\}\), are enumerated by the large Schroder numbers (and thus \(\{2143,3142,\tau\}\) with \(\tau\) as above is Wilf-equivalent to the set of patterns \(\{2413,3142\}\)). Burstein and Pantone proved the case…
Two vignettes on full rook placements
Using bijections between pattern-avoiding permutations and certain full rook placements on Ferrers boards, we give short proofs of two enumerative results. The first is a simplified enumeration of the -avoiding permutations, obtained recently by Callan via a complicated decomposition. The…
A refinement of Wilf-equivalence for patterns of length 4
In their paper, Dokos et al. conjecture that the major index statistic is equidistributed among \(1423\)-avoiding, \(2413\)-avoiding, and \(3214\)-avoiding permutations. In this paper we confirm this conjecture by constructing two major index preserving bijections, \(\Theta:S_n(1423)\to S_n(2413)\) and \(\Omega:S_n(2314)\to S_n(2413)\). In…
Pattern avoidance in matchings and partitions
Extending the notion of pattern avoidance in permutations, we study matchings and set partitions whose arc diagram representation avoids a given configuration of three arcs. These configurations, which generalize \(3\)-crossings and \(3\)-nestings, have an interpretation, in the case of matchings,…
Modified growth diagrams, permutation pivots, and the BWX map \phi^*
In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation \(\phi^*\), defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Melou and Steingrimsson proved the analogue of the main result of Backelin,…
A simple bijection between 231-avoiding and 312-avoiding placements
Stankova and West proved in 2002 that the patterns \(231\) and \(312\) are shape-Wilf-equivalent. Their proof was nonbijective. We give a new characterization of \(231\) and \(312\) avoiding full rook placements and use this to give a simple bijection that…
Another look at bijections for pattern-avoiding permutations
In [2] we proved that a natural bijection \(\Gamma:S_n(321) \rightarrow S_n(132)\) that Robertson defined by an iterative process in [8] preserves the numbers of fixed points and excedances in each \(\sigma\in S_n(321).\) The proof depended on first showing that \(\Gamma(\sigma^{-1})=(\Gamma(\sigma))^{-1}\)…
On bijections for pattern-avoiding permutations
Published: J. Combin. Theory Ser. A (116) 2009, 1271-1284.