International Journal of Combinatorics
Volume 2010 (2010), Article ID 751861, 10 pages
Research Article

The Distribution of the Size of the Union of Cycles for Two Types of Random Permutations

Mathematics Department, Occidental College, 1600 Campus Road, Los Angeles, CA 90041, USA

Received 28 August 2010; Accepted 5 October 2010

Academic Editor: Johannes Hattingh

Copyright © 2010 Tamás Lengyel. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.