重集上的排列
重集及其排列
定义：重集
允许元素重复的集合称为重集，通常表示为
$$ \left\lbrace 1^{m_1}, 2^{m_2},\cdots,n^{m_2} \right\rbrace $$
其中 \(m_i\) 表示元素 \(i\) 出现了 \(m_i\) 次.
重集的排列在概率论当中就已经探讨过，在此不进行赘述，仅作描述：
重集 \(\left\lbrace 1^{m_1}, 2^{m_2},\cdots,n^{m_2} \right\rbrace\) 上的排列个数为：
\[
\frac{(m_1+m_2+\cdots+ m_n)!}{m_1! m_2 ! \cdots m_n !}
\]
重集排列逆序数的生成函数
定义重集上排列的逆序数：相等的不算进逆序数，其余类似普通排列，例如
\[
\pi = 2121
\]
逆序数记为 \(\mathrm{inv}(\pi) = 3\) .
定理：重集排列逆序数的生成函数
重集 \(\left\lbrace 1^{m_1}, 2^{m_2},\cdots,n^{m_2} \right\rbrace\) 上排列的逆序数的生成函数满足以下公式：
$$ \sum\limits_{\pi}q^{\mathrm{inv}(\pi)} = \frac{[m_1+m_2+\cdots+m_n]!}{[m_1]![m_2]!\cdots [m_n]!} $$