tailieunhanh - Báo cáo toán học: "Generalized Descents and Normality"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Generalized Descents and Normality. | Generalized Descents and Normality Miklós Bóna Department of Mathematics University of Florida Gainesville FL 32611-8105 Submitted Jan 29 2008 Accepted Jun 11 2008 Published Jun 20 2008 Mathematics Subject Classification 05A16 Abstract We use Janson s dependency criterion to prove that the distribution of d-descents of permutations of length n converge to a normal distribution as n goes to infinity. We show that this remains true even if d is allowed to grow with n. 1 Introduction Let p p1p2 pn be a permutation. We say that the pair i j is a d-descent in p if i j i d and pi pj. In particular 1-descents correspond to descents in the traditional sense and n 1 -descents correspond to inversions. This concept was introduced in 2 by De Mari and Shayman whose motivation came from algebraic geometry. They have proved that if n and d are fixed and ck denotes the number of permutations of length n with exactly k d-descents then the sequence c0 c1 is unimodal that is it increases steadily then it decreases steadily. It is not known in general if the sequence c0 c1 is log-concave or not that is whether ck_1ck 1 ck holds for all k. We point out that in general the polynomial yk ckxk does not have real roots only. Indeed in the special case of d n 1 we get the well-known 1 identity ck x 1 x 1 x x . 1 x x k which has all nth roots of unity as roots. Indeed in this case a d-descent is just an inversion as we said above. In this paper we prove a related property of generalized descents by showing that their distribution converges to a normal distribution as the length n of our permutations goes to infinity. Our main tool is Janson s dependency criterion which is a tool to prove normality for sums of bounded random variables with a sparse dependency graph. While the proof itself is reasonably straightforward we find the very fact that Janson s criterion THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N21 1 is being applied to objects usually studied by algebraic not probabilistic .