bijective proof problems 选做（上）

pdf 版本的题目表

记号和声明.

注意双射意味着单和满。单往往是显然的，满则等价于唯一可逆。
$Y^X=X\rightarrow Y$ $X$ $Y$ 的映射。
$x\mapsto\xi$ $x$ $\xi$ 的映射。
$C(S,m)$ $S$ $m$ $\{f\in\{0,1\}^S,\sum_{i=1}^nf(i)=m\}$ 。
$[n]=\{1,2,...,n\}$ 。
$\#S$ $S$ 的大小。
$(c_1,c_2,...,c_n)$ $\mathbf c$ 。
既然是双射证明题集，此处所有问题的解答只允许使用组合意义bijective proof $S$ $T$ $|S|=|T|$ ）。被禁止的手段包括但不限于
- 归纳
- 递归 / 递推
- 生成函数
- 组合恒等式，即使该组合恒等式可以用组合意义证明
~~事实上很大概率你也用不了（悲）~~
另外还要尽量使证明足够优雅。
有可能会插入一些 EC 里的好题。
教程关皆是 EC 里的叙述，加入的原因是：如果读者不熟悉这部分的双射和结论，则很可能对下面的问题掉线。

问题难度解释.

$+$ $-$ 表示微调。
[1]：显然或直接。
[2]：困难或比较技巧性。[2+] 是应当给研究生留的作业题的难度上界。
[3]：极其困难。一些学生可能能做出 [3-]。几乎没有人可以在合理的时间内做出 [3]。（有时候用相对简单的方法做出 [3] 级题是可以发论文的……）
[*]：Open Problem。（草）
此处难度皆标注以题单中标注的难度。

基础部分

主要关于组合数。

5.[2]

问题.
$(S_1,...,S_k)$ $S_i$ $[n]$ 的子集。
$S_1\subseteq...\subseteq S_k$ 。
$S_i$ 两两不交。
$\bigcap S=\varnothing$ 。

解答.
$\{1\sim k +1\}^{[n]}$ $f(i)$ $i$ $S_{f(i)}$ $f(i)=k+1$ 表示从未出现。
$S_i\mapsto S_{i}/S_{i-1}$ 。
$\bigcup S=[n]$ $S_i\mapsto [n]/S_i$ $([k] 的非空子集)^{[n]}$ 的双射。
$\blacksquare$

开胃小菜，没啥好说的。

话说这不应该是 [1]？

12.[2-]

问题.
证明
$\sum_{k = 0}^{n} (\binom{x + k}{k}) = (\binom{x + n + 1}{n})$
$x$ $x$ 的有限次多项式，证明了正整数的情况也就证明了一般情况）

解答.
$C([x+n+1],n)$ $\mathbf S$ $(k, S)$ $S\in C(x+k,k)$ 。
$n-k$ $\mathbf S$ $1$ $S$ $[x+k]$ $\mathbf S(x+k+1)$ $0$ $S$ 描述。
$\blacksquare$

13.[3]

问题.
证明
$\sum_{k = 0}^{n} (\binom{2 k}{k}) (\binom{2 (n - k)}{n - k}) = 4^{n}$

解答.
$2n\choose n$ $(0,0)$ $(n,n)$ ，每一步只能向上一步或是向右一步的方案数（该双射是显然的）。
$(0,0)$ $2n$ $(k,S,T)$ $S$ $(0,0)$ $(k,k)$ $T$ $(0,0)$ $2n-2k$ $(0,0)$ 从未 $y=x$ $k$ $y=x$ 的位置。
$T$ ${2(n-k)\choose n-k}$ 。这一部分的说明不是我的解法而是来自于这里。
$2n$ $4$ 类：
$T$ 的一员
$S$ 的一员
$y=x$ $y=x$ 右方
$y=x$ $y=x$ 上方
$y=x$ ，不需要再做考虑。
剩下只是一些处理组合数的工作，略去不谈。
$\blacksquare$
$S$ $T$ 的双射。

14.[3-]

问题.
证明
$\sum_{i = 0}^{min (a, b)} (\binom{x + y + i}{i}) (\binom{y}{a - i}) (\binom{x}{b - i}) = (\binom{x + a}{b}) (\binom{y + b}{a})$

解答.
不妨改为证明
$\sum_{i = 0}^{min (a, b)} (\binom{x + y + i}{x, y, i}) (\binom{y}{a - i}) (\binom{x}{b - i}) = (\binom{x + y}{x}) (\binom{x + a}{b}) (\binom{y + b}{a})$
$4$ 维网格上走动，每次可以选择
$(0,1,0,1)$
$(1,0,0,0)$
$(1,1,0,0)$
$(0,0,1,0)$
$(0,0,1,1)$
$(x,a,y,b)$ 。求总方案数。
$x$ $a$ $b$ $y$ 。
然后到这里我就做不下去了……还是 EIls 靠谱。
其实和上面的思路是一样的，但是 EIls 的解释确实更容易联系到右式。剩下的工作已经很显然了。
$\blacksquare$

15.[3-]

问题.
证明
$\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} x^{k} = \sum_{k = 0}^{n} (\binom{2 n - k}{n - k, n - k, k}) (x - 1)^{k}$

解答.
$(S,T,f)$ $S,T\subseteq [n]$ $f$ $S$ $[x]$ 的映射。
$(S',T',f')$ $S'\subseteq[n]$ $T'\in C([2n]/S,n)$ $f'$ $S'$ $[x-1]$ 的映射。
$(S,T,f)\mapsto(S',T',f')$ ：
$S'=f^{-1}([x-1])$ ；
$f'$ $f$ $S'$ 上的限制；
$T'$ $[n]$ $[n]/S$ $[n+1....2n]$ $T$ 平移到此处。
$\blacksquare$

16.[3-]

问题.
证明
$\sum_{i + j + k = n} (\binom{i + j}{i}) (\binom{j + k}{j}) (\binom{k + i}{k}) = \sum_{r = 0}^{n} (\binom{2 r}{r})$

解答.
不会，贺了题解。
$(\alpha,\beta,\gamma)$ 的数量：
$\alpha$ $\text{a}$ $\text{b}$ $i+1$ $\text{a}$ $j+1$ $\text{b}$ 。
$\beta$ $j+1$ $j+k+1$ 。
$\gamma$ $i+1$ $i+k+1$ 。
做如下映射：
$\alpha$ $i$ $\text{a}$ $\text{c}^{\gamma_i}\text{d}$ $i$ $b$ $\text{d}^{\beta_i}\text{c}$ $\text{c}^r$ $r$ $\text{c}$ 。
$\alpha$ $\text{c}$ $\text{d}(\text{dc})^r$ （满足该形式的后缀显然是唯一的）的形式结尾。删掉它们。
这构建了一个从左到右的双射。（其逆并不非常复杂，留给读者）
$\blacksquare$

就离谱，这双射是人能想出来的？建议评分 [3+]

**66.[*]**

问题.
证明，
$\frac{(2 m)! (2 n)!}{m! n! (m + n)!}$
总是整数。
$\blacksquare$

解答.
这个问题在 2014 年得到了解决。

置换和循环

排列 / 置换显然是一个重要的话题：没有排列 / 置换我们就无从描述一大类等价。

教程关：置换和循环.

问题.
$(c_1,c_2,...,c_n)$ $c_1$ $1$ $c_2$ $2$ $[n]\rightarrow [n]$ 的置换的数量为
$(\binom{n}{c_{1}, c_{2}, . . ., c_{n}}) \prod_{i} \frac{1}{i^{c_{i}}}$

解答.
$\mathfrak S^{\mathbf c}_{[n]}$ $\mathbf c$ 的置换。
故而只需要证明
$n! = # S_{[n]}^{c} \prod_{i} i^{c_{i}} c_{i}!$
$\mathfrak S_{[n]}$ 到自身的双射，被称为基本双射。ctrl+F 搜索本网页的“基本双射”，你就会知道为何它配得上如此称号。
$w$ 的所有循环写为以其最大元素开头，称为代表元素，然后以代表元素的大小排列各循环。最后删掉括号。
$w=4271367=(14)(2)(375)(6)$ $2416753$ 。
$\mathfrak S_{[n]}\rightarrow\mathfrak S_{[n]}^{\mathbf c}$ $c_1$ $2c_2$ $2$ $\mathbf c$ $\prod_{i}i^{c_i}c_i!$ 。
先从任意一个原像出发。首先我们可以任意排列长度相等的循环，然后每个循环还可以旋转，显然这样生成的所有排列两两不同，于是便得证了。
$\blacksquare$

51.[3]

问题.
$D(n)$ $n$ 的错排数，证明：
$D (n) = n D (n - 1) + (- 1)^{n}$

解答.
比较复杂，参见：A bijective proof of a derangement recurrence。
$\blacksquare$

57 && EC 117.[2+]

问题.
$[n]$ $w$ $1$ $k$ 的概率。

解答.
$k$ $\frac 1n$ 。
$1$ $1$ $k$ $1$ $k$ $[n-1]$ 的排列的双射。
$\blacksquare$

EC 120.[2+]

问题.
$E_k(n)$ $[n]$ $k$ $E_k(n)=\dfrac{1}{k}$ 。

解答.
$E_k(n)=\dfrac 1k\sum_{i=1}P(i 所在循环大小为 k)=\dfrac 1k$ 。
$\blacksquare$

58 && EC118.

问题.
$w$ $[n]$ $1,2$ $\dfrac 12$ 。
$1,...,\lambda_1$ $\lambda_1+1,...,\lambda_1+\lambda_2$ $1,...,\lambda_1$ $\lambda_{\ell}$ ，其出现概率为
$P_{λ} = \frac{\prod (λ - 1)!}{(\sum λ)!}$
$w$ $[n]$ 的偶置换中选取。证明概率为
$Q_{λ} = \frac{\prod (λ - 1)!}{(- 2 + \sum λ)!} \cdot (\frac{1}{(\sum λ - 1) \sum λ} + \frac{(- 1)^{n - l}}{(n - 1) n})$

解答.
对于 (a)，解法是显然的。
$w_1$ $w_2$ $1,2$ $1,2$ 不在同一个循环的排列。
对于 (b)，我们还是考虑基本双射。为了方便稍稍修改其为：把最小的元素固定为循环开头，把循环按最小元素降序排列。
$1$ $2$ 之前出现。
思考如何扩展到此处：只需要：
$2,...,\lambda$ $1$ 之后出现；
$\lambda_1+2,...,\lambda_1+\lambda_2$ $\lambda_1+1$ $\lambda_1+1,...,\lambda_1+\lambda_2$ $1$ 之前出现；
……
剩下的工作已经显然了。
对于 (c)，我们做如下考虑。
$w$ $v$ $v$ $v'=(v_2,v_1,v_3,v_4,....,v_n)$ 恰有一个奇置换和一个偶置换。
$v,v'$ $v_1,v_2$ $v_1,v_2$ $v_1,v_2$ 反转了后者所在循环的长度奇偶性，也就反转了整个置换的奇偶性。
$v'$ 满足条件，则
$v$ 也满足条件；
$v_2=\lambda_1+...+\lambda_{\ell-1}+1$ $v_2<v_1\le \sum \lambda$ 。
剩下的部分已经显然了。

76[2] && 77[3].

问题.
证明：
$k\ge 2$ $[n]$ 的排列的数量为
$\prod_{i = 1}^{n} (n - i + [k | i])$
不 $k\ge 2$ $[n]$ 的排列的数量为
$\prod_{i = 1}^{n} (i - [k | i])$

解答.
对于 76 只需要做如下考虑：
$w(1)$ $n-1$ $1$ ）。
$w(w(1)),w(w(w(1)))$ $n-2,n-3$ ……种选择。
$w^{\left<k\right>}(1)$ $n-k$ $1$ $1$ $w(i)$ 开始继续流程。
$\prod_{i=1}^n(n-i+[k\ |\ i])$ 的直接双射。
对于 77……我所能找到的唯一一份文献复杂得离谱，而我根本找不到别的做法。实在是没办法了。
$\blacksquare$

置换和等价类

等价类的研究和应用。

18.[3]

问题.
$n$ 为质数时，下面两个集合的元素个数相等。
$n$ $0$ $[0...n-1]$ 的子集
$n$ 个珠子的黑白项链在旋转变换下的等价类

解答.
$\dfrac{2(n-1)+2^n}n$ 。
后者比较显然。
$\times n$ $[2]^{[n]}$ ：
显然两个不同等价类形成的像不会相同
$n$ 是质数，这种情况只在该项链全黑或全白时出现，减掉即可
稍微扩展一下便是 Burnside 引理的一个组合证明。
再来考虑前者。
$i$ $1$ 再取模。
$i\neq 0\land i\neq n$ $i$ $[0...n-1]$ $d$ $d+i\bmod n$ 的集合，从而它们的元素个数相等。即两两
$i=0\lor i = n$ 时不成立，特判即可。
$\blacksquare$

原题要求证明任意奇数的情况，所以评到了 [3]。原话：This is easy if n is prime.

被 D 傻了（悲）

$q$ $n,q$ 互质的一般情况的双射。~~为什么近年来发数数论文的看名字全是中国人或华裔，难道这是血统加成？~~

21[2].

问题.
$p$ $a^p-a$ $p$ $0$ 。

解答.
$a^p-a$ $p$ 。
$S$ $[a]^{[p]}$ 中值不全相同的映射。
相信读者对 18 一定还有印象，于是一个显然的分组是把所有循环同构的映射分为一类。
$\blacksquare$

22.a.[2]

问题.
$p$ ${2p\choose p}-2$ $p^2$ 整除。

解答.
$S$ $(0,0)$ $(p,p)$ ，且不完全贴着边框走的方案数。
$p$ $p$ $p^2$ ，得证。
$\blacksquare$

下面是一道我自己加的题目。

EXTRA-1.[2]

问题.
建议阅读这个课件或对生成函数有一定了解后再来尝试此题。
$\mathcal G$ $g=(f_1,f_2,...)$ $\ell(g)$ $f$ $\mathcal F$ 中的元素。
证明
$\sum_{g \in G} \prod_{i} x t_{f_{i}} = exp (\sum_{i = 1}^{\infty} \frac{x^{i}}{i} \sum_{f \in F} t_{f}^{i})$
$t_{f},x$ 皆是形式幂级数变元。
$t_f=y^{|f|},x=1$ 的特殊情况。

解答.
$\text{exp}$ 在有标号计数中体现出的组合意义（如果要精确描述势必会极占篇幅，所以干脆不描述了，想必读者在阅读完课件之后肯定能独立研究出），我们希望两边都可以写成指数生成函数的形式。
具体来说，把左式强行写成：
$\sum_{n \geq 1} n! G_{n} \frac{x^{n}}{n!}$
$G_n=\sum_{\ell(g)=n}\prod_{i}t_{f_i}$ $g$ $w$ 组成的有序对。
右边则可这样考虑：
$\sum_{i=1}^{\infty}(i-1)!\dfrac{x^i}{i!}$ 可解释为所有循环。
考虑 exp 的组合意义，循环的 exp 自然就是排列。
$h$ $v$ $v$ $f$ $t_f$ 的权值。
基本双射 $w$ $g$ 染色，然后逆向使用基本双射。显然这个变换是保权值的，于是我们便证明了原定理。
$\blacksquare$

排列上的统计（statistics）

一个排列可能有极多的特征，其中一些特征神奇地有着极其紧密的联系。

教程关：逆序对，Descents，和 Major index（上）&& 70.

定义.
$\text{inv}(w)$ 。
$D(w)=\{w_i>w_{i+1},i\in[n-1]\}$ 。
$\text{maj}(w)=\sum_{i\in D(w)}i$ 。

问题.
$\mathbf{inv}$ 和 $\mathbf{maj}$ 是等分布（equidistribution）的。换句话说
$# {w \in S_{n}, inv (w) = k} = # {w \in S_{n}, maj (w) = k}$

~~A direct bijective proof would be of great interest.jpg~~ $n$ $n-1$ 时的映射。

解答.
$\phi:\{w\in\mathfrak S_n,\text{maj}(w)=k\}\rightarrow\{w\in\mathfrak S_n,\text{inv}(w)=k\}$ 。
$v=\phi((w_1,w_2,...,w_{n-1}))$ 。
$v$ $\phi(w)$ ：
$w_{n-1}<w_n$ ：
$\phi(w)$ $w_n$ 的位置后面切一刀。
把所有部分向右循环移一位。
否则，
$\phi(w)$ $w_n$ 的位置后面切一刀。
把所有部分向右循环移一位。
$\phi_{n}(w)=w_n$ 。
$\phi$ 显然是可逆的。
$\text{maj}(w)=\text{inv}(\phi(w))$ 。
$n=1$ 显然成立。
$\text{maj}((w_1,w_2,...,w_{n-1})=\text{inv}(v)$ 。
$w_{n-1}<w_{n}$ $v$ 的逆序对数不变。
首先我们不必考虑不同部分之间的影响，因为它们之间根本没有相对位置改变。
$l$ $l-1$ $>w_n$ $<w_n$ $l-1$ 。
$n-1-\#\{i:w_i<w_n\}=\#\{i:w_i>w_n\}$ $w_n$ 代来的影响抵消。
$w_{n-1}>w_n$ 的部分，这和上面的证明完全一样。
$\blacksquare$

教程关：逆序对，Descents，和 Major index（中）.

定义.
$\text{ID}(w)=D(w^{-1})$ $w$ $(w_1,w_2,...,w_n)$ $f(\min w)=w_1,...,f(\max w)=w_n$ 即可。

问题.
$\phi$ $\text{ID}$ $\text{ID}(w)=\text{ID}(\phi(w))$ 。

解答.
$\text{ID}$ 还可如此解释：
$w$ $1$ $2$ $3$ ……如果根本不存在就跳过。
$n$ 便立即结束。
$w$ $\text{ID}(w)$ 。
$\text{ID}$ 的基础定义显然是直接一致的。不过它的确更直观。
下面我们开始证明原命题。
$n=1$ 显然成立。
$\text{ID}((w_1,w_2,...,w_{n-1}))=\text{ID}(v)$ 。
$w_{n-1}$ $w_n$ 来讨论。
$w_{n-1}<w_n$ ：
$w$ $\phi(w)$ $w_n$ $w_n$ 没区别。
$w_n$ $w_{n-1}$ $w_n$ $\phi_n(w)$ 也是如此。我们还需要核对接下来的行为。
$\phi_n(w)$ $w_i>w_n$ 的元素之间的相对顺序，于是便得证了。
$w_{n-1}>w_n$ $n$ 开始反向查找得到的结果相同），我们反着读即可。
$\blacksquare$

教程关：逆序对，Descents，和 Major index（下）&& 71.

定义.
$\text{imaj}(w)=\text{maj}(w^{-1})$ 。

问题.
$\mathbf{inv}$ 和 $\mathbf{maj}$ 和 $\mathbf{imaj}$ 是两两交对称分布（symmetric joint distribution）的。换句话说
$# {w \in S_{n}, inv (w) = j, maj (w) = k} = # {w \in S_{n}, inv (w) = k, maj (w) = j}$ $# {w \in S_{n}, inv (w) = j, imaj (w) = k} = # {w \in S_{n}, inv (w) = k, imaj (w) = j}$ $# {w \in S_{n}, maj (w) = j, imaj (w) = k} = # {w \in S_{n}, maj (w) = k, imaj (w) = j}$

解答.
$\text{maj}$ $\text{imaj}$ $w\mapsto w^{-1}$ $\text{maj}$ $\text{imaj}$ 。
$\phi$ $\text{ID}$ $\text{maj}$ 的。于是便立即得证。
$\blacksquare$

63.[2+] && 64.[2-]

问题.
excedance $w_i>i$ 的位置的数量。证明，excedance 的数量和 descents 的数量是等分布的。
weak excedance $w_i\ge i$ 的位置）的数量满足
$# {w \in S_{n}, wexc (w) = k} = # {w \in S_{n}, des (w) = k - 1}$

解答.
$w$ $w'$ $w'(i)<w'(i+1)$ 当且仅当：
$w(w'(i))\neq w'(i+1)$ $w'(i)$ 是循环的结尾）
$w(w'(i))=w'(i+1)\land w'(i+1)>w'(i)$ 。
$w'(i)\le w(w'(i))$ 。
$w'(i)\le w(w'(i))$ $w'(i)<w'(i+1)\lor {\color{red}i=n}$ 。
总结：
$n - des (w^{'}) = wexc (w)$
至此我们证明了，
$# {w \in S_{n}, wexc (w) = k} = # {w \in S_{n}, des (w) = n - k}$
$\text{des}(w)\mapsto n-1-\text{des}(w)$ ，我们已然证明了 64。
$\phi_i(w)=n+1-w_{n+1-i}$ ，它使得
$n - wexc (w) = exc (ϕ (w))$
$\blacksquare$

$\mathbf w$ - 兼容性（compatibility）（上）.

定义.
$f:[n]\rightarrow\mathbb N$ 是 $\mathbf w$ - 兼容的，如果：
$f(w_1)\ge f(w_2)\ge ...\ge f(w_n)$ ；
$w_i>w_{i+1}$ $f(w_i)>f(w_{i+1})$ 。

问题.
$f:[n]\rightarrow\mathbb N$ 总是与且只与某个排列兼容。

解答.
$f$ 分成数段。
$f(i_1)=f(i_2)=...=f(i_{\ell})$ $\{i_1,i_2,...,i_{\ell}\}$ $\{w_l,w_{l+1},...,w_r\}$ $w_i<w_{i+1}$ $f$ 兼容的排列。
$\blacksquare$

$\mathbf w$ - 兼容性（compatibility）（下）.

定义.
$\mathcal A(w)=\{f:[n]\rightarrow \mathbb N,f\ 兼容于\ w\}$ 。
$\mathcal A_m(w)=\{f\in[n]^{[m]},f\ 兼容于\ w\}$ 。

问题.
(a) 证明，
$# A_{m} (w) = (\binom{m + n - 1 - des (w)}{n})$
(b) 证明，
$\sum_{f \in A (w)} x^{\sum_{i = 1}^{n} f (i)} = \frac{x^{maj (w)}}{(1 - x) (1 - x^{2}) . . . (1 - x^{n})}$

解答.
$w_i>w_{i+1}$ $1\sim i$ $-1$ $m-\text{des}(w)\ge g(w_1)\ge g(w_2)\ge ...\ge g(w_n)\ge 1$ 的函数的双射，剩下的工作已经显然了。
$g(w_1)\ge g(w_2)\ge ...\ge g(w_n)\ge 0$ 的双射，同时显然有
$\sum_{i = 1}^{n} f (i) = maj (w) + \sum_{i = 1}^{n} g (i)$
$\dfrac{1}{(1-x)(1-x^2)...(1-x^n)}$ $\mathcal A_{n=k}(w)$ $\mathcal A_{n=k}(w)\cup A_{n=k-1}(w)$ 的双射：
$0$ ，删掉这个元素。
$-1$ 。
$\dfrac{1}{1-x^k}$ $k$ $k$ $x^{jk}$ $k$ $j$ $-1$ 。
$\blacksquare$

65.[3-]

问题.
记
$A (n, k) = # {w \in S_{n}, wexc (w) = k}$
证明：
$\sum_{n \geq 0} n^{k} x^{n} = \frac{\sum_{i = 1}^{k} A (k, i) x^{i}}{(1 - x)^{k + 1}}$

解答.
我们只需要证明，
$n^{k} = \sum_{i = 1}^{k} A (k, i) (\binom{k + n - i}{n - i})$
$n^k$ $[n]^{[k]}$ ，联系到教程关（上），我们容易写出
$n^{k} = \sum_{w \in S_{k}} # A_{n} (w)$
应用教程关（下）便得证了。
$\blacksquare$

此题在 bijective proof problems 中出现时几乎没有给出关于 w- 兼容性的介绍（只给了一个简短的 note 介绍定义），故评到了 [3-]。

多重集的排列

为了研究划分我们必须先介绍一下。

教程关：多重集排列.

定义.
$\mathbf{(n)!}$ $\dfrac{1-q}{1-q}\cdot\dfrac{1-q^2}{1-q}\cdot\ldots\cdot\dfrac{1-q^n}{1-q}$ 。
记
$(\binom{n}{a_{1}, a_{2}, . . ., a_{m}}) = \frac{(n)!}{(a_{1})! (a_{2})! . . . (a_{m})!}$
注意类似于组合数的记号是有一定原因的，比如有
$(\binom{n}{k}) = (\binom{n - 1}{k}) + q^{n - k} (\binom{n - 1}{k - 1})$
$q=1$ 时这个记号回到正常的组合数。所以这个记号被我们叫做组合数的 q-模拟。q-模拟当然是有其价值的，但那就是另一个故事了。这里我们只是借用一下它的符号。
${\mathbf n\choose \mathbf k}$ $\mathbb F_q^n$ $k$ 维线性子空间的数量。
$M$ $a_i$ $i$ $\{1^{a_1},2^{a_2},....,m^{a_m}\}$ $|M|\rightarrow m$ $a_i$ $i$ 。
$\sum_{i<j}[w_i<w_j]$ 。

问题.
证明
$\sum_{w \in S_{M}} q^{inv (w)} = (\binom{n}{a_{1}, a_{2}, . . ., a_{m}})$

解答.
$\phi$ ：
$\begin{matrix} S_{M} \times S_{[a_{1}]} \times S_{[a_{2}]} \times \dots \times S_{[a_{m}]} \overset{ϕ}{\to} S_{| M |} \\ (w_{0}, w_{1}, w_{2}, . . ., w_{m}) \overset{ϕ}{\mapsto} w \end{matrix}$
$w_0(i)$ $j$ $w_0(i)$ $\mathfrak w(i)=w_{w_0(i)}(j)+\sum_{d<w_0(i)}a_d$ 。
$\text{inv}(\mathfrak w)=\text{inv}(w_0)+\text{inv}(w_1)+...$ ，于是就得证了。
$\blacksquare$

to be continued...