The Distribution of the Size of the Union of Cycles for Two Types of Random Permutations. (10th October 2010) - Lengyel, Tamás
Abstract : We discuss some problems and permutation statistics involving two different types of random permutations. Under the usual model of random permutations, we prove that the shifted coverage of the elements of{ 1, 2, …, k } of a random permutation over{ 1, 2, …, n } ; that is, the size of the union of the cycles containing these elements, excluding these elements themselves, follows a negative hypergeometric distribution. This fact gives a probabilistic model for the coverage via the canonical cycle representation. For a different random model, we determine some random permutation statistics regarding the problem of the lost boarding pass and its variations.