Compositions with a fixed number of inversions (Q2420605)

The major index of a permutation $\sigma$ of $\{1,\ldots, m\}$ is defined to be the sum of the indices $i \in \{1,\ldots, m-1\}$ such that $\sigma$ has a descent in position $i$; that is, $\sigma(i) > \sigma(i+1)$. An inversion of a permutation $\sigma$ is a pair $\{i,j\}$ such that $i < j$ and $\sigma(i) > \sigma(j)$. \textit{P. A. MacMahon} [Am. J. Math. 35, 281--322 (1913; JFM 44.0076.02)] proved that the numbers of permutations of $\{1,\ldots, n\}$ having exactly $k$ inversions and having major index $k$ are the same, for all $k$. In the paper under review, the authors use the generalization of MacMahon's result to compositions. (Writing a composition as $(\sigma_1, \ldots, \sigma_m)$ the definitions of inversions and the major index carry over.) In their first main result, they find that the generating function for compositions of $n$ with a unique inversion is \[ \sum_{i_1=2}^\infty z_{i_1} \sum_{i=1}^{i_1-1} \frac{z^i}{(1-z^{i+1})(1-z^{i+2}) \ldots }. \] By the generalized MacMahon result, this is also the generating function for compositions of $n$ with a unique descent. Such compositions have the form $(\sigma_1, \sigma_2, \ldots, \sigma_m)$ where $(\sigma_2, \ldots, \sigma_m)$ is a partition with parts written in increasing order. The generating function is therefore \[ \frac{z}{1-z} (P(z)-1) - \bigl( P(z) - \frac{1}{1-z} \bigr), \] where the second factor corrects for counting compositions with $\sigma_1 < \sigma_2$, and $P(z) = \prod_{i=1}^\infty (1-z^i)^{-1}$ is the usual generating function for partitions. Equating the two expressions the authors obtain the identity \[ \sum_{i_1=2}^\infty z_{i_1} \sum_{i=1}^{i_1-1} \frac{z^i}{(1-z^{i+1})(1-z^{i+2}) \ldots } = \frac{2z-1}{1-z}P(z) + 1. \] In the remainder of \S 2, the authors give similar identities obtained by enumerating compositions with $2$, $3$, $4$ and $5$ inversions, and a scheme for producing such identities for each fixed number $r$ of inversions. The final \S 3 of the paper gives asymptotic estimates using the framework established in [\textit{P. J. Grabner} et al., Comb. Probab. Comput. 23, No. 6, 1057--1086 (2014; Zbl 1304.11123)]. In particular, Theorem 3.3 states that the number of compositions of $n$ with precisely $r$ inversions is asymptotically equal to \[ \frac{1}{r!} \bigl( \frac{\sqrt{6n}}{\pi} \bigr)^r p(n), \] where $p(n)$ is the number of partitions of $n$.