Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 .
