Attacks and alignments: rooks, set partitions, and permutations

Abstract

We consider uniformly random set partitions of size $n$ with exactly $k$ blocks, and uniformly random permutations of size $n$ with exactly $k$ cycles, under the regime where $n-k\sim t\sqrt{n}$, $t>0$. In this regime, there is a simple approximation for the entire process of component counts; in particular, the number of components of size 3 converges in distribution to Poisson with mean $\frac{2}{3}{t}^2$ for set partitions and mean $\frac{4}{3}{t}^2$ for permutations, and with high probability all other components have size one or two. These approximations are proved, with preasymptotic error bounds, using combinatorial bijections for placements of $r$ rooks on a triangular half of an $n\times n$ chess board, together with the Chen--Stein method for processes of indicator random variables.

21 pages, 3 figures. To appear in Australasian Journal of Combinatorics