Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A Combinatorial Proof of the Log-concavity of a famous sequence counting permutations"
Đ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 trên tạp chí toán học quốc tế đề tài: A Combinatorial Proof of the Log-concavity of a famous sequence counting permutations. | A Combinatorial Proof of the Log-concavity of a famous sequence counting permutations Miklos Bona Submitted Nov 24 2004 Accepted Jan 11 2005 Published Jan 24 2005 Mathematics Subject Classifications 05A05 05A15 To Richard Stanley who introduced me to the area of log-concave sequences. Abstract We provide a combinatorial proof for the fact that for any fixed n the sequence i n k 0 k n of the numbers of permutations of length n having k inversions is log-concave. 1 Introduction Let p p1p2 pn be a permutation of length n or in what follows an n-permutation. An inversion of p is a pair i j of indices so that i j but pi pj. The enumeration of n-permutations according to their number i p of inversions and the study of numbers i n k of n-permutations having k inversions is a classic area of combinatorics. The best-known result is the following 4 . Theorem 1.1 Let n 2. Then we have _ _ CD X x p X i n k xk 1 x 1 x x2 1 x x2 xn-1 -p2Sn k 0 Another classic result 3 is that the numbers i n k also count n-permutations having major index k. Details about this result and other related results can be found in 1 . University of Florida Gainesville FL 32611-8105. Partially supported by an NSA Young Investigator Award. Email bona@math.ufl.edu. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2 2005 N2 1 A somewhat less explored property of the numbers i n k is log-concavity. The sequence ak o k m is called log-concave if akak 2 a2 1 for all k. See 5 for a classic survey of log-concave sequences and see 2 for an update on that survey. A polynomial is called log-concave if its coefficients form a log-concave sequence. It is a classic result see for instance 1 for a proof that the product of log-concave polynomials is log-concave. Therefore Theorem 1.1 immediately implies that the polynomial P 2Q i n k xk is logconcave that is the sequence i n 0 i n 1 i n 2 is log-concave. We could not hnd any previous proof of this fact that does not use generating functions. In this paper we will provide .