Unseparated pairs and fixed points in random permutations
Report Number
822
Abstract
In a uniform random permutation Π of [n] := {1, 2, . . . , n}, the set
of elements k ∈ [n − 1] such that Π(k + 1) = Π(k) + 1 has the same distribution
as the set of fixed points of Π that lie in [n−1]. We give three different proofs of
this fact using, respectively, an enumeration relying on the inclusion-exclusion
principle, the introduction of two different Markov chains to generate uniform
random permutations, and the construction of a combinatorial bijection. We
also obtain the distribution of the analogous set for circular permutations that
consists of those k ∈ [n] such that Π(k + 1 mod n) = Π(k) + 1 mod n. This
latter random set is just the set of fixed points of the commutator [ρ, Π], where
ρ is the n-cycle (1, 2, . . . , n). We show for a general permutation η that, under
weak conditions on the number of fixed points and 2-cycles of η, the total
variation distance between the distribution of the number of fixed points of
[η, Π] and a Poisson distribution with expected value 1 is small when n is large.
PDF File