Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

Suppose μ and ν are integer partitions of n, and N>n. It is well known that the Ferrers boards associated to μ and ν are rook-equivalent iff the multisets [μi+i:1⩽i⩽N] and [νi+i:1⩽i⩽N] are equal. We use the Garsia–Milne involution principle to produce a bijective proof of this theorem in which non-attacking rook placements for μ are explicitly matched with corresponding placements for ν. One byproduct is a direct combinatorial proof that the matrix of Stirling numbers of the first kind is the inverse of the matrix of Stirling numbers of the second kind. We also prove q-analogues and p,q-analogues of these results. We also use the Garsia–Milne involution principle to show that for any two rook boards B and B′, if B and B′ are bijectively rook-equivalent, then B and B′ are bijectively hit-equivalent.