Normal approximations for descents and inversions of permutations of multisets
Mark Conger, Divakar Viswanath · arXiv (Cornell University) · 2005
Normal approximations for descents and inversions of permutations of the set $\{1,2,...,n\}$ are well known. A number of sequences that occur in practice, such as the human genome and other genomes, contain many repeated elements. Motivated by such examples, 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\leq i π(j)$. The number of descents is the number of $i$ in the range $1\leq 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\to\infty$, 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