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, West, and Xin in the context of involutions, and in so doing they needed to prove that \(\phi^*\) commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Melou and Steingrimsson asked if \(\phi^*\) might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of \(\phi^*\), by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and \(\phi^*\).
Published: J. Combin. Theory Ser. A (119) 2012, 1280-1298, arXiv.