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:1iN] and ν_i+i:1iN] 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.