کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4624660 1631635 2014 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unseparated pairs and fixed points in random permutations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Unseparated pairs and fixed points in random permutations
چکیده انگلیسی

In a uniform random permutation Π   of [n]:={1,2,…,n}[n]:={1,2,…,n}, the set of elements k∈[n−1]k∈[n−1] such that Π(k+1)=Π(k)+1Π(k+1)=Π(k)+1 has the same distribution as the set of fixed points of Π   that lie in [n−1][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]k∈[n] such that Π(k+1modn)=Π(k)+1modn. This latter random set is just the set of fixed points of the commutator [ρ,Π][ρ,Π], where ρ is the n  -cycle (1,2,…,n)(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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 61, October 2014, Pages 102–124
نویسندگان
, , ,