# §26.16 Multiset Permutations

Let $S=\{1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}}\}$ be the multiset that has $a_{j}$ copies of $j$, $1\leq j\leq n$. $\mathfrak{S}_{S}$ denotes the set of permutations of $S$ for all distinct orderings of the $a_{1}+a_{2}+\cdots+a_{n}$ integers. The number of elements in $\mathfrak{S}_{S}$ is the multinomial coefficient (§26.4) $\genfrac{(}{)}{0.0pt}{}{a_{1}+a_{2}+\cdots+a_{n}}{a_{1},a_{2},\ldots,a_{n}}$. Additional information can be found in Andrews (1976, pp. 39–45).

The definitions of inversion number and major index can be extended to permutations of a multiset such as $351322453154\in\mathfrak{S}_{\{1^{2},2^{2},3^{3},4^{2},5^{3}\}}$. Thus $\mathop{\mathrm{inv}}(351322453154)=4+8+0+3+1+1+2+3+1+0+1=24$, and $\mathop{\mathrm{maj}}(351322453154)=2+4+8+9+11=34.$

The $q$-multinomial coefficient is defined in terms of Gaussian polynomials (§26.9(ii)) by

 26.16.1 $\genfrac{[}{]}{0.0pt}{}{a_{1}+a_{2}+\cdots+a_{n}}{a_{1},a_{2},\ldots,a_{n}}_{q% }=\prod_{k=1}^{n-1}\genfrac{[}{]}{0.0pt}{}{a_{k}+a_{k+1}+\cdots+a_{n}}{a_{k}}_% {q},$

and again with $S=\{1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}}\}$ we have

 26.16.2 $\displaystyle\sum_{\sigma\in\mathfrak{S}_{S}}q^{\mathop{\mathrm{inv}}(\sigma)}$ $\displaystyle=\genfrac{[}{]}{0.0pt}{}{a_{1}+a_{2}+\cdots+a_{n}}{a_{1},a_{2},% \ldots,a_{n}}_{q},$ 26.16.3 $\displaystyle\sum_{\sigma\in\mathfrak{S}_{S}}q^{\mathop{\mathrm{maj}}(\sigma)}$ $\displaystyle=\genfrac{[}{]}{0.0pt}{}{a_{1}+a_{2}+\cdots+a_{n}}{a_{1},a_{2},% \ldots,a_{n}}_{q}.$