Bruhat Order on Fixed-Point-Free Involutions in the Symmetric Group

Abstract

We provide a structural description of Bruhat order on the set $F_{2n}$ of fixed-point-free involutions in the symetric group $S_{2n}$ which yields a combinatorial proof of a combinatorial identity that is an expansion of its rank-generating function. The decomposition is accomplished via a natural poset congruence, which yields a new interpretation and proof of a combinatorial identity that counts the number of rook placements on the Ferrers boards lying under all Dyck paths of a given length $2n$. Additionally, this result extends naturally to prove new combinatorial identities that sum over other Catalan objects: 312-avoiding permutations, plane forests, and binary trees.