A simple bijection between 231-avoiding and 312-avoiding placements

MaRDI QIDQ2875888zbMATH OpenFDO

Authors Jonathan Bloom, Dan Saracino

Publication date 12 August 2014

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

zbMATH Keywords

Ferrers boardrook placementWilf-equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Review text

Denote by \(S_F(\tau)\) the set of all full rook placements on a Ferrers board \(F\) that avoid a permutation \(\tau\). It was proved by \textit{Z. Stankova} and \textit{J. West} [J. Algebr. Comb. 15, No. 3, 271--290 (2002; Zbl 1005.05002)], that the patterns 231 and 312 are shape-Wilf-equivalent, meaning, \(|S_F(231)|=|S_F(312)|\).NEWLINENEWLINEThe authors present a new proof for this result, this time providing a bijection. They associate a sequence of integers to a rook placement \(P\) in a Ferrers board \(F\), denoted \(S(P,F)\). Then, they prove that for \(P\in S_F(231)\) or \(P\in S_F(312)\), this sequence, along with the Ferrers board \(F\), determines the placement \(P\) by building explicitly the placement from the sequence and \(F\) (Theorem 1).NEWLINENEWLINEAfterwards, they define 231-conditions and 312-conditions for sequences and present a way to obtain other sequences satisfying these conditions from sequences in \(S_F(231)\) and \(S_F(312)\). A bijection is established between sequences satisfying the 231-conditions and sequences satisfying the 312-conditions and finally this bijection is carried to the sets \(S_F(231)\) and \(S_F(312)\) (Theorem 3).

Recommendations

• Patterns in matchings and rook placements
• Two vignettes on full rook placements
• Pattern avoidance in matchings and partitions
• The rook numbers of Ferrers boards and the related restricted permutation numbers
• Bijections on m-level Rook Placements
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Invisible permutations and rook placements on a Ferrers board
• A graph theory of rook placements
• On Garsia-Remmel problem of rook equivalence
• Bijections on m-level rook placements

Cited in

(8)

• On (shape-)Wilf-equivalence for words
• Pattern avoidance in matchings and partitions
• Classification of bijections between 321- and 132-avoiding permutations
• A simple bijection between 312-avoiding permutations and triangulations
• Two vignettes on full rook placements
• Bijections on m-level rook placements
• An infinite family of inv-Wilf-equivalent permutation pairs
• Patterns in matchings and rook placements

This page was built for publication: A simple bijection between 231-avoiding and 312-avoiding placements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875888)