About the Project
26 Combinatorial AnalysisProperties

§26.16 Multiset Permutations

Let S={1a1,2a2,,nan} be the multiset that has aj copies of j, 1jn. 𝔖S denotes the set of permutations of S for all distinct orderings of the a1+a2++an integers. The number of elements in 𝔖S is the multinomial coefficient (§26.4) (a1+a2++ana1,a2,,an). 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𝔖{12,22,33,42,53}. Thus inv(351322453154)=4+8+0+3+1+1+2+3+1+0+1=24, and 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 [a1+a2++ana1,a2,,an]q=k=1n1[ak+ak+1++anak]q,

and again with S={1a1,2a2,,nan} we have

26.16.2 σ𝔖Sqinv(σ) =[a1+a2++ana1,a2,,an]q,
26.16.3 σ𝔖Sqmaj(σ) =[a1+a2++ana1,a2,,an]q.