26 Combinatorial Analysis Properties 26.15 Permutations: Matrix Notation 26.17 The Twelvefold Way

§26.16 Multiset Permutations

ⓘ

Defines:: $\genfrac{[}{]}{0.0pt}{}{\NVar{a_{1}}+\NVar{a_{2}}+\dots+\NVar{a_{n}}}{\NVar{a_% {1}},\NVar{a_{2}},\ldots,\NVar{a_{n}}}_{\NVar{q}}$ : $q$ -multinomial coefficient
Keywords:: inversion numbers, major index, multiset, permutations, $q$ -multinomial coefficient
Notes:: See Andrews (1976, pp. 39–45).
Permalink:: http://dlmf.nist.gov/26.16
See also:: Annotations for Ch.26

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},$
ⓘ Symbols: $\genfrac{[}{]}{0.0pt}{}{\NVar{n}}{\NVar{m}}_{\NVar{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $\genfrac{[}{]}{0.0pt}{}{\NVar{a_{1}}+\NVar{a_{2}}+\dots+\NVar{a_{n}}}{\NVar{a_% {1}},\NVar{a_{2}},\ldots,\NVar{a_{n}}}_{\NVar{q}}$ : $q$ -multinomial coefficient, $k$ : nonnegative integer, $n$ : nonnegative integer, $a_{j}$ : numbers and $q$ : parameter Permalink: http://dlmf.nist.gov/26.16.E1 Encodings: TeX, pMML, png See also: Annotations for §26.16 and Ch.26

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},$
ⓘ Symbols: $\in$ : element of, $\genfrac{[}{]}{0.0pt}{}{\NVar{a_{1}}+\NVar{a_{2}}+\dots+\NVar{a_{n}}}{\NVar{a_% {1}},\NVar{a_{2}},\ldots,\NVar{a_{n}}}_{\NVar{q}}$ : $q$ -multinomial coefficient, $\mathfrak{S}_{\NVar{n}}$ : set of permutations of $\{1,2,\ldots,n\}$ , $n$ : nonnegative integer, $a_{j}$ : numbers, $S$ : multiset and $q$ : parameter Permalink: http://dlmf.nist.gov/26.16.E2 Encodings: TeX, pMML, png See also: Annotations for §26.16 and Ch.26
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}.$
ⓘ Symbols: $\in$ : element of, $\genfrac{[}{]}{0.0pt}{}{\NVar{a_{1}}+\NVar{a_{2}}+\dots+\NVar{a_{n}}}{\NVar{a_% {1}},\NVar{a_{2}},\ldots,\NVar{a_{n}}}_{\NVar{q}}$ : $q$ -multinomial coefficient, $\mathfrak{S}_{\NVar{n}}$ : set of permutations of $\{1,2,\ldots,n\}$ , $n$ : nonnegative integer, $a_{j}$ : numbers, $S$ : multiset and $q$ : parameter Permalink: http://dlmf.nist.gov/26.16.E3 Encodings: TeX, pMML, png See also: Annotations for §26.16 and Ch.26

26.15 Permutations: Matrix Notation 26.17 The Twelvefold Way

NIST

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov