Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§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. \mathop{\mathfrak{S}_{{S}}\/}\nolimits 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 \mathop{\mathfrak{S}_{{S}}\/}\nolimits is the multinomial coefficient (§26.4) \multinomial{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\mathop{\mathfrak{S}_{{\{1^{2},2^{2},3^{3},4^{2},5^{3}\}}}\/}\nolimits. 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