Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: An interesting new Mahonian permutation statistic. | An interesting new Mahonian permutation statistic Mark C. Wilson Department of Computer Science University of Auckland Private Bag 92019 Auckland New Zealand mcw@ Submitted Jul 21 2010 Accepted Oct 21 2010 Published Oct 29 2010 Mathematics Subject Classification Primary 05A05. Secondary 68W20 68W40 68Q25. Abstract The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic DIS that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics des and exc appear to coincide with any known Euler-Mahonian pair. A general construction of Skandera yields an Eulerian partner eul such that eul DIS is equidistributed with des MAJ . However eul itself appears not to be a known Eulerian statistic. Several ideas for further research on this topic are listed. 1 The statistic Random permutations The standard algorithm Knu81 Algorithm P for uniformly generating a random permutation of n 1 . n is as follows. Start with the identity permutation I 1. n in the symmetric group Sn. There are n steps labelled n n 1 . 1 the last step can be omitted but it makes our notation easier to include it here . At step i a random position ji is chosen uniformly from i and the current element in position ji is swapped with the element at position i. Example 1. The permutation 25413 G S5 is formed by choosing j5 3 j4 1 j3 1 j2 1 ji 1- Its inverse 41532 is formed by choosing j5 2 j4 3 j3 2 j2 1 ji 1- Thanks to Frank Ruskey Mark Skandera Einar Steingrimsson and Kyle Petersen for useful discussions. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R147 1 In terms of multiplication in Sn n is a product of transpositions IL n ji - Any of these transpositions may be the identity permutation. This representation as a triangular product gives a bijection between Sn and the set of sequences j1 . jn that satisfy 1
