Normal Approximations for Descents and Inversions of Permutations of Multisets

Normal approximations for descents and inversions of permutations of the set {1,2,…,n} are well known. We consider the number of inversions of a permutation π(1),π(2),…,π(n) of a multiset with n elements, which is the number of pairs (i,j) with 1≤i<j≤n and π(i)>π(j). The number of descents is the number of i in the range 1≤i<n such that π(i)>π(i+1). We prove that, appropriately normalized, the distribution of both inversions and descents of a random permutation of the multiset approaches the normal distribution as n→∞, provided that the permutation is equally likely to be any possible permutation of the multiset and no element occurs more than α n times in the multiset for a fixed α with 0<α<1. Both normal approximation theorems are proved using the size bias version of Stein’s method of auxiliary randomization and are accompanied by error bounds. This work was supported by a research fellowship from the Sloan Foundation.